[DFS-BFS] SWEA : 14413_격자판 칠하기

Source URL : SWEA : 14413_격자판 칠하기

문제 요구사항 :

N X M 크기의 직사각형 격자판이 있다. 격자판의 각 칸은 1 x 1 크기의 정사각형 모양이다. 당신은 이 격자판의 각 칸을 검은색 또는 흰색으로 칠할 계획이다.
당신은 격자판의 칸 중 몇 개(0개 이상 NM개 이하)는 검은색으로 칠할지 흰색으로 칠할지를 이미 정해 놓았다.
정확히 표현하자면, N X M 크기의 행렬 A가 있어서, Ai,j 가 ‘#’라면 격자판의 i행 j열에 있는 칸은 검은색으로 칠해야 하고, Ai,j 가 ‘.’라면 격자판의 i행 j열에 있는 칸은 흰색으로 칠해야 하며, Ai,j 가 ‘?’라면 격자판의 i행 j열에 있는 칸은 검은색으로 칠해도 되고 흰색으로 칠해도 된다.
당신은 아직 색이 정해지지 않은 칸들을 어떤 색으로 칠할지를 잘 정한 뒤 격자판을 색칠할 것이다.
색칠한 결과 격자판의 인접한 (즉, 변 하나를 공유하는) 두 칸의 색이 항상 다르게 할 수 있는지를 판단하는 프로그램을 작성하라.

[입력]

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 두 개의 자연수 N과 M(1 ≤ N ≤50, 1 ≤ M ≤ 50)이 공백 하나를 사이로 두고 주어진다.
다음 N개의 줄에는 '#', '.', '?'로만 구성된 길이가 M인 문자열이 하나씩 주어지며, 이는 행렬 A를 나타낸다.

[출력]

각 테스트 케이스마다, '?'에 해당하는 칸의 색을 잘 정하여, 격자판의 인접한 두 칸의 색이 항상 서로 다르게 할 수 있다면 ‘possible’을, 그렇지 않다면 ‘impossible’을 출력한다.

접근 방법 :

BFS와 DFS 풀이 방법이 있다. DFS가 좀 더 문제에 접근하기 쉽고, BFS의 경우 조건처리가 까다롭다
코드 디버깅 에러 한 군데를 자꾸 못 찾아서 14번 도전 하고서야 찾음...

문제의 부분

// 잘못된 예 - BFS
        if (ch == '#')
            map[xx][yy] = '.';
        else
            map[xx][yy] = '#';   // 이러면 물음표일 때도 #으로 바꿔버림

// 잘못된 예 - DFS
if (map[nx][ny] == '?') {
            if (map[x][y] == '#') {
                map[nx][ny] = '.';
                dfs(nx, ny);
            }
            else if (map[nx][ny] == '.') {  // x y 좌표에 접근해야 하는데 왜 nx ny에 접근하는가....
                map[nx][ny] = '#';
                dfs(nx, ny);
            }
        }

풀이 순서 :

TC를 입력받아 해당 TC만큼 반복한다.
N과 M을 입력받아 N M 크기만큼의 문자를 입력 받는다.
BFS의 경우
- 입력 받을 때 물음표의 위치를 queue에 저장해둔다.
- 해당 큐 사이즈만큼 bfs 탐색을 돌며 격자판을 칠한다.
- 다 끝난 후 격자판을 체크하여 문제 조건에 맞으면 possible, 아니면 impossible을 출력한다.
DFS의 경우
- 모든 입력을 받은 후, DFS 탐색을 한다.
- 다음 칸이 ?라면, 현재 칸이 #이냐 .이냐에 따라 반대되는 것으로 색칠하고, dfs탐색을 해당 nx ny로 한다.
- 다음 칸이 ?가 아니고, 지금 칸과 다음 칸의 값이 같다면, dfs 탐색을 종료하도록 한다.
- 탐색이 중간에 종료 됐다면, impossible을 출력하고, 아니라면 계속 탐색해 나간다.

inseonyun / Algorithm

[DFS-BFS] SWEA : 14413_격자판 칠하기 #67