[백준 / Java] 17090번 미로 탈출하기

사용한 알고리즘 (DFS)

DFS 

https://cobi-98.tistory.com/30

[필수 알고리즘] DFS 깊이 우선 탐색 (Stack 구조) 이해

 

🔒 17090번 미로 탈출하기

✔ 문제 설명

🚩 요구사항 분석

• U (x-1, y) 좌
• R (x,y+1) 상
• D (x+1,y) 우
• L (x,y-1) 하
• 미로의 경계 밖으로 나가면 count
• 탈출하지 못한다면 (방문을 하였다면), 다음 칸으로 이동

 

🔑 문제풀이

해당 문제는 message , x, y 값을 확인하여 칸을 이동하면서 이동하기 전 현재위치, maze [x][y] 값을 true를 주면서 문자를 읽어나간다. 

방문했던 곳이라면 retrun 해주고  미로의 범위에서 나간다면(탈출한다면) count를 해 나가는 문제이다.

 

넘어오는 문자를 확인하여 dfs를 호출해나가는데  해당 문자에 맞게 x-1, x+1, y-1, y+1을 해서 미로를 헤쳐나가면 된다.

// 시간초과 
public class Main {
    public static int N;
    public static int M;
    public static int count;
    public static String[][] maze;
    public static boolean[][] visit;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        maze = new String[N][M];
        visit = new boolean[N][M];
        for (int i = 0; i < N; i++) {
            String stMessage = br.readLine();
            for (int j = 0; j < M; j++) {
                maze[i][j] = String.valueOf(stMessage.charAt(j));
            }
        }
        count = 0;
        for (int i = 0; i < N; i++) {

            for (int j = 0; j < M; j++) {
                if (!visit[i][j]) {
                    dfs(maze[i][j], i, j);
                }
            }
        }

        System.out.println(count);
    }

    public static void dfs(String message, int x, int y) {

        // 방문했던곳이면
        if (visit[x][y]) {
            return;
        }

        visit[x][y] = true;
        if (message.equals("U")) {
            if (x - 1 < 0) {
                count++;
                visit[x][y] = false;
                return;
            }
            dfs(maze[x - 1][y], x - 1, y);
            visit[x][y] = false;

        } else if (message.equals("R")) {
            if (y + 1 == M) {
                count++;
                visit[x][y] = false;
                return;
            }
            dfs(maze[x][y + 1], x, y + 1);
            visit[x][y] = false;
        } else if (message.equals("D")) {
            if (x + 1 == N) {

                count++;
                visit[x][y] = false;
                return;
            }
            dfs(maze[x + 1][y], x + 1, y);
            visit[x][y] = false;

        } else if (message.equals("L")) {
            if (y - 1 < 0) {

                count++;
                visit[x][y] = false;
                return;
            }
            dfs(maze[x][y - 1], x, y - 1);
            visit[x][y] = false;
        }
    }
}

 

이렇게 한다면 다음과 같이 시간초과가 뜰 것이다. 그럼 시간을 줄일 수 있는 방법이 무엇일까? 를 많이 고민해 봤다.

 

탈출할 수 있는 경로 maze[0][0]

만약 maze [0][0]을 탈출할 수 있는 경로로 기억해 놓으면 

maze[1][1]의 경로 추적

maze [0][0]에 오면 count를 하는 방식으로,

탈출할 수 있는 경로면 count ++ 하고 아니면 다음 재귀를 호출하는 방식을 이용해 보았다.

 

그렇기에 memory라는 탈출경로를 기억할 변수를 추가하여  만약 지나서 빠져나간 경로라면 count를 해주고

아니면 dfs를 호출하는 방식으로 코드를 수정하였다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static int N;
    public static int M;
    public static int count;
    public static String[][] maze;
    public static boolean[][] visit;

    public static boolean[][] memory;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        maze = new String[N+2][M+2];  // 미로 범위
        visit = new boolean[N+2][M+2];
        memory = new boolean[N+2][M+2];
        for (int i = 1; i <= N; i++) {
            String stMessage = br.readLine();
            stMessage = " "+stMessage+" ";
            for (int j = 1; j <= M; j++) {
                maze[i][j] = String.valueOf(stMessage.charAt(j));
            }
        }
        count = 0;
        for (int i = 1; i <= N; i++) {

            for (int j = 1; j <= M; j++) {

                if (memory[i][j]) {
                    count++;
                }else{
                    dfs(maze[i][j], i, j);
                }
            }
        }

        System.out.println(count);
    }

    public static void dfs(String message, int x, int y) {

        // 방문했던곳이면
        if (visit[x][y]) {
            visit[x][y] = false;
            memory[x][y] = false;
            return;
        }

        // 지나서 빠져나간 경로라면
        if(!(x >= 1 && y >= 1 && x <= N && y <= M) || memory[x][y]){ //경계를 벗어나거나 한번 지나온곳이면 count+1하고 리턴
            memory[x][y] = true;
            count++;
            return;
        }

        visit[x][y] = true;
        memory[x][y] = true;
        if (message.equals("U")) {
            dfs(maze[x - 1][y], x - 1, y);
            if (!memory[x - 1][y]) {
                memory[x][y] = false;
            }

        } else if (message.equals("R")) {

            dfs(maze[x][y + 1], x, y + 1);
            if (!memory[x][y + 1]) {
                memory[x][y] = false;
            }
        } else if (message.equals("D")) {

            dfs(maze[x + 1][y], x + 1, y);
            if (!memory[x + 1][y]) {
                memory[x][y] = false;
            }

        } else if (message.equals("L")) {

            dfs(maze[x][y - 1], x, y - 1);
            if (!memory[x][y - 1]) {
                memory[x][y] = false;
            }
        }
        visit[x][y] = false;
    }
}

 

 

그러면 해당 문제를 풀 수 있었다. 시간이 많이 걸렸는데 이 시간을 줄이는 방법을 더 생각해봐야 할 것이다.