[BOJ] 백준 17090 : 미로 탈출하기 (java)

🧪 17090 미로 탈출하기

---

난이도 : 🌟 골드 3
유형 : BackTracking (DFS)

17090번: 미로 탈출하기

 

📝 문제

---

크기가 N×M인 미로가 있고, 미로는 크기가 1×1인 칸으로 나누어져 있다. 미로의 각 칸에는 문자가 하나 적혀있는데, 적혀있는 문자에 따라서 다른 칸으로 이동할 수 있다.

어떤 칸(r, c)에 적힌 문자가

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

미로에서 탈출 가능한 칸의 수를 계산해보자. 탈출 가능한 칸이란, 그 칸에서 이동을 시작해서 칸에 적힌대로 이동했을 때, 미로의 경계 밖으로 이동하게 되는 칸을 의미한다.

 

입력

 

첫째 줄에 미로의 크기 N, M(3 ≤ N, M ≤ 500)이 주어진다. 둘째 줄부터 N개의 줄에는 미로의 각 칸에 적힌 문자가 주어진다.

 

출력

 

첫째 줄에 탈출 가능한 칸의 수를 출력한다.

 

🚧  주의할 점

---

1. dfs로만 접근하게 된다면 시간초과가 발생한다 → 백트래킹으로 모든 해를 검사하지 않고 탈출하는 경로 기록을 통해 더 빠르게 탈출할 수 있도록 한다.

 

실행초과 코드

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

public class Main {

    static int n, m, cnt;
    static char[][] maze;
    static boolean[][] visited;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    public static void main(String[] args) throws IOException {

        // BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedReader br = new BufferedReader(new FileReader("input.txt"));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        maze = new char[n][m];

        for (int i = 0; i < n; i++) {
            String word = br.readLine();
            for (int j = 0; j < m; j++) {
                maze[i][j] = word.charAt(j);
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                visited = new boolean[n][m];
                dfs(maze[i][j], i, j);
            }
        }

        System.out.println(cnt);

        br.close();
    }

    private static void dfs(char dir, int x, int y) {

        visited[x][y] = true;

        int nx = x + dx[dirIndex(dir)];
        int ny = y + dy[dirIndex(dir)];

        if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
            cnt++;
            return;
        }

        if (!visited[nx][ny]) {
            dfs(maze[nx][ny], nx, ny);
        }
    }

    private static int dirIndex(char dir) {

        if (dir == 'D') {
            return 1;
        } else if (dir == 'U') {
            return 0;
        } else if (dir == 'L') {
            return 2;
        } else {
            return 3;
        }
    }
}

 

🧐 핵심 로직

---

1. 탈출 혹은 탈출했던 경로인 경우
   • 탈출 시 거쳐간 경로 기록
   • 탈출 가능 카운트 올리기
2. 방문처리된 경로를 만난 경우
   • 방문 처리가 되어있는데 1번을 거쳐왔다는 의미는 탈출이 불가능한 경로라는 의미이기 때문에 탈출 불가
3. 탈출 시 거쳐간 모든 경로 true 기록

 

💻 최종 코드 (256 ms)

---

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

public class Main {

    static int n, m, cnt;
    static char[][] maze;
    static boolean[][] visited, depth;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    public static void main(String[] args) throws IOException {

        // BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedReader br = new BufferedReader(new FileReader("input.txt"));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        maze = new char[n][m];
        visited = new boolean[n][m];
        depth = new boolean[n][m];

        for (int i = 0; i < n; i++) {
            String word = br.readLine();
            for (int j = 0; j < m; j++) {
                maze[i][j] = word.charAt(j);
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                backTracking(maze[i][j], i, j);
            }
        }

        System.out.println(cnt);

        br.close();
    }

    private static boolean backTracking(char dir, int x, int y) {

        visited[x][y] = true;

        int nx = x + dx[dirIndex(dir)];
        int ny = y + dy[dirIndex(dir)];

        if ((nx < 0 || nx >= n || ny < 0 || ny >= m) || depth[nx][ny]) {
            depth[x][y] = true;
            cnt++;
            return true;
        }

        if (visited[nx][ny]) {
            return false;
        }

        return depth[x][y] = backTracking(maze[nx][ny], nx, ny);
    }

    private static int dirIndex(char dir) {

        if (dir == 'D') {
            return 1;
        } else if (dir == 'U') {
            return 0;
        } else if (dir == 'L') {
            return 2;
        } else {
            return 3;
        }
    }
}