[ 백준 12887번 ] 경로 게임

1. 문제

 

12887번: 경로 게임

 

2. 풀이

문제가 다속 복잡해보이기 위해 노력했으나 사실 핵심을 간파하기는 쉬운 유형이다.

 

격자판의 하얀색 칸을 검정색 칸으로 바꾼 경우에도 왼쪽-오른쪽 경로가 존재할 수도 있다. 이때, 왼쪽-오른쪽 경로가 존재하면서 바꿀 수 있는 하얀색 칸의 최댓값을 구하는 프로그램을 작성하시오.

왼쪽-오른쪽 경로가 항상 존재하는 게임판만 입력으로 주어진다.

 

이를 다시 정리하자면, 좌측 끝에서 우측 끝으로 가는 경로에서 방문하지 않은 칸의 개수를 최대로 만들라는 말이며, 이는 곧 최소경로를 찾으라는 말과 동일하다. 그렇다면 우리는 아래의 과정을 통해서 본 문제를 풀 수 있게 된다.

 

• 입력과 동시에, '하얀색' 칸의 개수를 세어둔다.
  • 향후 방문한 최소 경로의 길이를 빼주기 위함
• map[0][0], map[1][0] 중 흰색 칸을 모두 시작점으로 잡아 BFS를 돌린다.
• 최소 경로를 찾은 경우, 첫 번째 과정을 수행하기 위해 1을 더해 반환한다.
  • 방문하지 않은 칸을 모두 검정으로 바꿔야 하는데 시작 노드 역시 방문한 노드이므로 1을 더해줌
  • (경로 탐색 시, 경로의 값을 1로 두고 풀이하면 불필요한 과정)

 

세부 구현은 아래 코드를 참고하자.

 

3. 소스코드

public class Main {
    static final int[] dy = {-1, 0, 1, 0};
    static final int[] dx = {0, 1, 0, -1};
    static final char WHITE = '.', BLACK = '#';
    static char[][] map;
    static int M;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        M = Integer.parseInt(br.readLine());

        map = new char[2][M];
        int white = 0;
        for (int i = 0; i < 2; i++) {
            String line = br.readLine();
            for (int j = 0; j < M; j++) {
                map[i][j] = line.charAt(j);
                if (map[i][j] == WHITE) {
                    white++;
                }
            }
        }

        int shortestLength = bfs();

        System.out.println(white - shortestLength + "");
        br.close();
    }

    static int bfs() {
        int len = 0;

        Queue<Integer> q = new LinkedList<>();
        boolean[][] visit = new boolean[2][M];
        for (int i = 0; i < 2; i++) {
            if (map[i][0] == WHITE) {
                q.add(i * M);
                visit[i][0] = true;
            }
        }

        while (!q.isEmpty()) {
            int size = q.size();

            while (size-- > 0) {
                int now = q.poll();
                int y = now / M;
                int x = now % M;

                if (x == M - 1) {
                    return len + 1;
                }

                for (int dir = 0; dir < 4; dir++) {
                    int ny = y + dy[dir];
                    int nx = x + dx[dir];

                    if (ny < 0 || nx < 0 || 2 <= ny || M <= nx || visit[ny][nx] || map[ny][nx] == BLACK) continue;

                    visit[ny][nx] = true;
                    q.add(ny * M + nx);
                }
            }

            len++;
        }

        return len;
    }

}

 

GitHub - kwanik-kor/BOJ: Baekjoon Online Judge - explanation of solved problems and complete code