[ 백준 1799 ] 비숍 (C++)

백준의 비숍(1799) 문제이다.

( 문제 바로가기 )

[ 문제풀이 ]

1) 이 문제는 대각선으로만 움직일 수 있는 비숍들을 놓을 수 있는 칸들에 대해서 비숍끼리 서로 안 잡아먹고 최대 몇 개 까지

   놓을 수 있는지 구하는 문제이다.

   시간제한이 10초인데도 불구하고, 본인은 풀다보니 시간초과가 뜨기도 했다. 시간초과를 해결하기 위해서 여러가지 방법을

   도전해보다가, 맵을 2개로 나누어서 생각해보았다.

   체스판은 검은색지점과 흰색 지점이 있다.

   이런식으로 체스판은 구현되어 있다.

   잘 생각해보면, 어떤 검은색 칸에 비숍을 놓아도, 흰색칸에 있는 비숍에게는 절대 영향을 끼치지 못한다.

   물론 반대의 경우도 똑같다.

   본인은 이렇게 검은색에 놓을 수 있는 비숍의 최대갯수 + 흰색에 놓을 수 있는 비숍의 최대갯수를 따로 구해서 더해서 최댓

   값을 구하였다.

2) 먼저 문제를 풀기전에, 본인이 사용한 배열들에 대해서 설명하겠다.

   MAP[][] 2차원배열과, MAP_Color[][] 2차원배열,  Select[][] 2차원 배열 총 3개의 2차원 배열을 사용하였다.

   MAP[][]은 비숍을 놓을 수 있는 칸인지 아닌지, 즉 우리가 입력받는 맵의 상태를 받는 배열이다.

   MAP_Color[][]는 검은색은 1로, 흰색은 0으로 표시해주는 검은색과 흰색을 구분하는 배열이다.

   Select[][] 배열은 특정 좌표에 비숍에 놓아지면 true로 표시, 아니면 false로 비숍을 놓았는지 안 놓았는지를 판단하는

   2차원 배열이다.

   따라서, 같은 함수에 대해서 검은색칸과 흰색 칸 총 2번의 호출을 통해서 문제를 풀어나갈 것이다.

   문제를 풀어야할 때 고려해야 할 것들에 대해서 알아보자.

   1. 현재 내가 생각하는 칸에 대한 것인지?

     → 검은색 칸에 대해서 비숍을 놓고 있으면, 내가 현재 접근하는 칸이 검은색 칸인지?

   2. 놓을 수 있는 칸인지?

     → 비숍이 갈 수 있는 칸들을 탐방하면서, 다른 비숍이 있는지 없는지?

  

   위의 2가지를 유의하면서 문제를 풀어보자.

3) 백트래킹을 이용해서 풀이를 구현해보았다. 위에서도 설명했지만 비숍을 놓을 수 있는 조건은 이러하다.

   1. 지금 비숍을 놓으려는 좌표가 내가 설정한 색깔인지 ??

   2. 입력으로 비숍을 놓을 수 있는 자리인지??

   3. 해당 정점에 비숍을 놓았을 때, 대각선들을 탐색했을 때, 다른 비숍이 없어서 이 자리에 놓을 수 있는지?

   위의 3가지 조건을 모두 만족한다면, 해당 정점에 비숍을 놓아주고, Select[][] 배열을 통해서 놓았다는 표시를 해주면

   된다.

   이런식으로 흰색칸, 검은색칸 총 2번의 탐색을 통해서 각 색깔의 최대갯수를 더해주면 최댓값이 된다.

[ 소스코드 ]

#include<iostream>
#include<cstring>
#include<vector>
 
#define endl "\n"
#define MAX 10
using namespace std;
 
int N, Answer[2];
int MAP[MAX][MAX], MAP_Color[MAX][MAX];
bool Select[MAX][MAX];
 
int Bishop_PosNum;
 
int dx[] = { -1, -1, 1, 1 };
int dy[] = { -1, 1, -1, 1 };
 
void Input()
{
    memset(MAP_Color, 0, sizeof(MAP_Color));
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> MAP[i][j];
            if (i % 2 == 0)
            {
                if (j % 2 == 0) MAP_Color[i][j] = 1;
            }
            else
            {
                if (j % 2 == 1) MAP_Color[i][j] = 1;
            }
        }
    }
}
 
void Print(int x, int y)
{
    cout << "################################################" << endl;
    cout << "[ " << x << " , " << y << " ] 에 의해서 맵이 이렇게 바뀝니다." << endl;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (Select[i][j] == true) cout << 1 << " ";
            else cout << 0 << " ";
        }
        cout << endl;
    }
    cout << "################################################" << endl;
}
 
void Check_MAP(int x, int y, bool C)
{
    if (C == true)
    {
        MAP[x][y] = 2;
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            while (1)
            {
                if (nx < 0 || ny < 0 || nx >= N || ny >= N) break;
                if (MAP[nx][ny] == 1) MAP[nx][ny] = 2;
                nx = nx + dx[i];
                ny = ny + dy[i];
            }
        }
    }
    else
    {
        MAP[x][y] = 1;
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            while (1)
            {
                if (nx < 0 || ny < 0 || nx >= N || ny >= N) break;
                if (MAP[nx][ny] == 2) MAP[nx][ny] = 1;
                nx = nx + dx[i];
                ny = ny + dy[i];
            }
        }
    }
//    Print(x, y);    
}
 
bool Can_Position(int x, int y)
{
    for (int i = 0; i < 2; i++)
    {
        int nx = x;
        int ny = y;
        while (1)
        {
            if (nx < 0 || ny < 0 || nx >= N || ny >= N) break;
            if (Select[nx][ny] == true) return false;
            nx = nx + dx[i];
            ny = ny + dy[i];
        }
    }
    return true;
}
 
void DFS(int Idx, int Cnt, int Color)
{
    if (Answer[Color] < Cnt) Answer[Color] = Cnt;
 
    for (int i = Idx + 1; i < N * N; i++)
    {
        int x = i / N;
        int y = i % N;
 
        if (MAP_Color[x][y] != Color || MAP[x][y] == 0 || Can_Position(x,y) == false) continue;
        Select[x][y] = true;
        DFS(i, Cnt + 1, Color);
        Select[x][y] = false;
    }
}
 
void Solution()
{
    DFS(-1, 0, 0);
    DFS(-1, 0, 1);
    cout << Answer[0] + Answer[1] << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}