백준 - 17090 미로 탈출하기(Java)

백트랙킹 문제입니다.

 

N*M 미로에서 각 위치마다 움직일 수 있는 방향이 정해져있습니다.

• U인 경우에는 (r-1, c)로 이동
• R인 경우에는 (r, c+1)로 이동
• D인 경우에는 (r+1, c)로 이동
• L인 경우에는 (r, c-1)로 이동

즉, 상하좌우에 따라 움직인다는 말입니다.

 

각 위치마다 움직일 수 있는 방향이 정해졌으므로,

처음 지나가는 길에 탈출할 수 있는 길인지 아닌지를 기록해두면,

이미 한 번 지나갔던 길에 도달하면 끝까지 다시 탐색을 할 필요가 없습니다.

 

예제 입력 2번으로 설명 드리겠습니다.

예제 입력 2번은 다음 그림과 같습니다.

위 그림에서 (0, 0)을 먼저 탐색하면 다음 그림과 같습니다.

지나간 길은 탐색 결과를 반환하여 저장하면 됩니다.(dfs)

다음으로 (0, 1)을 탐색하면 다음과 같습니다.

(0,1)에서 시작하는 탐색은 (1,0)을 지나가게 되는데,

이미 지나간 길이기 때문에 끝 까지 탐색할 필요 없이 기록된 값을 통해 지나갈 수 있는지 없는지 확인할 수 있습니다.

 

※[주의]

밖으로 나갈 수 없는 경우는 내부에서 사이클이 생기는 경우이기 때문에, 한 번 방문한 노드는 재 방문하지 않게 해야 합니다.

 

[구현 코드]

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    private static final int[] dx = {-1, 1, 0, 0}; // 상, 하, 좌, 우
    private static final int[] dy = {0, 0, -1, 1};

    private static int[][] map;
    private static boolean[][] depths, visited;
    private static int n, m = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stz = new StringTokenizer(br.readLine(), " ");

        n = Integer.parseInt(stz.nextToken());
        m = Integer.parseInt(stz.nextToken());

        map = new int[n][m];
        depths = new boolean[n][m];
        visited = new boolean[n][m];

        // 방향에 따라 설정한 값을 넣음
        for (int i = 0; i < n; i++) {
            char[] chrs = br.readLine().toCharArray();
            for (int j = 0; j < m; j++) {
                if(chrs[j] == 'U'){
                    map[i][j] = 0;
                } else if(chrs[j] == 'D'){
                    map[i][j] = 1;
                }else if(chrs[j] == 'L'){
                    map[i][j] = 2;
                }else{
                    map[i][j] = 3;
                }
            }
        }

        // 백트랙킹
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                backTracking(i, j);
            }
        }

        // 저장된 값을 통해 해당 위치가 밖으로 탈출 할 수 있는지 확인
        int answer = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if(depths[i][j]) answer++;
            }
        }

        bw.write(String.valueOf(answer));

        bw.flush();
        bw.close();
        br.close();
    }

    private static boolean backTracking(int x, int y) {
        visited[x][y] = true;

        int nx = x + dx[map[x][y]];
        int ny = y + dy[map[x][y]];
        
        // 백트랙킹
        // 이전에 지나갔으면서, 밖으로 탈출 할 수 있는 경우 
        if(!(nx>=0 && ny>=0 && nx<n && ny <m) || depths[nx][ny]) {
            depths[x][y] = true;
            return true;
        }
        
        // 이전에 지나갔갔으면서, 밖으로 탈출할 수 없는 경우(사이클)
        if(visited[nx][ny]) return false;

        // 이전의 값을 저장해 탈출 할 수 있는지 없는지 저장함
        return depths[x][y] = backTracking(nx, ny);
    }
}