[백준]#9944 NxM 보드 완주하기

문제

×M 보드 위에서 할 수 있는 게임이 있다. 보드는 크기가 1×1인 정사각형 칸으로 나누어져 있다. 보드의 각 칸은 빈 칸 또는 장애물이다. 장애물은 아래 그림에선 어두운 사각형으로 표시되어져 있다.

게임을 시작하려면 보드의 빈 칸 위에 공을 하나 놓아야 한다. 아래 그림에서 공은 회색 점으로 표시되어져 있다. 게임은 단계로 이루어져 있고, 각 단계는 아래와 같이 구성되어져 있다.

• 위, 아래, 오른쪽, 왼쪽 중 방향 하나를 고른 다음, 그 방향으로 공을 계속해서 이동시킨다.
• 공은 장애물, 보드의 경계, 이미 공이 지나갔던 칸을 만나기 전까지 계속해서 이동한다.

게임은 공이 더 이상 이동할 수 없을 때 끝난다. 이 때, 모든 빈 칸을 공이 방문한 적이 있어야 한다.

아래 그림은 총 10단계 만에 모든 칸을 방문하는 방법이다.

보드의 상태가 주어졌을 때, 모든 칸을 방문하기 위한 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에는 보드의 크기를 나타내는 N과 M이 주어진다. N은 세로 크기, M은 가로 크기이고, 두 값은 30보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 상태가 주어진다. 보드의 상태는 장애물을 나타내는 '*'과 빈 칸을 나타내는 '.'으로 이루어져 있다.

입력으로 주어진 보드가 장애물로만 이루어진 경우는 없다.

출력

각 테스트 케이스마다 보드의 모든 빈 칸을 방문하는 최소 이동 횟수를 출력한다. 출력 형식은 예제를 참고한다.

만약, 모든 빈 칸을 방문할 수 없다면 최소 이동 횟수는 -1이다. 가능한 이동 경로의 수는 1,000,000개를 넘지 않는다.

예제 입력 1

5 5
**...
.....
....*
..*..
.....
3 4
****
*...
*..*

예제 출력 1

Case 1: 10
Case 2: 3

풀이

이 문제는 dfs(깊이 우선 탐색) 알고리즘과 백트래킹을 이용해서 풀 수 있었다. 이 문제는 EOF 처리방법을 알아야 정확히 구현할 수 있다.

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static char[][] map;
    static boolean[][] visited;
    static int N;
    static int M;
    static int max_sum;
    static int ans;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = null;
        int test_case = 1;

        while((input=br.readLine()) != null) {
            String[] str = input.split(" ");
            N = Integer.parseInt(str[0]);
            M = Integer.parseInt(str[1]);
            max_sum = 0;
            ans = Integer.MAX_VALUE;

            map = new char[N][M];
            visited = new boolean[N][M];

            for(int i=0; i<N; i++) {
                input = br.readLine();
                for(int j=0; j<M; j++) {
                    map[i][j] = input.charAt(j);
                    if(map[i][j]=='.')
                        max_sum++;
                }
            }

            for(int i=0; i<N; i++) {
                for(int j=0; j<M; j++) {
                    if(map[i][j]=='.') {
                        visited[i][j] = true;
                        dfs(i, j, 1, 0);
                        visited[i][j] = false;
                    }
                }
            }

            if(ans== Integer.MAX_VALUE)
                ans = -1;
            System.out.println("Case "+test_case+": "+ans);
            test_case++;
        }
    }

    public static void dfs(int x, int y, int sum, int cnt) {
        if(sum==max_sum) {              //모든 칸을 지나왔을 경우 
            ans = Math.min(ans, cnt);
            return;
        }

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

            while(nx>=0 && nx<N && ny>=0 && ny<M && !visited[nx][ny] && map[nx][ny]=='.') {     //멈출 떄까지 나아가는 경우
                visited[nx][ny] = true;
                s++;
                nx += dx[i];
                ny += dy[i];
            }

            nx -= dx[i];
            ny -= dy[i];

            if(nx==x && ny==y) continue;

            dfs(nx, ny, s, cnt+1);

            while(nx!=x || ny!=y) {         //방문했던 좌표 회복
                visited[nx][ny] = false;
                nx -= dx[i];
                ny -= dy[i];
            }
        }
    }
}