백준 2178 - 미로 탐색

문제

 

 

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

 

 

 

코드

 

 

import java.io.BufferedReader;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;

public class Main {

    private static int N, M, result = Integer.MAX_VALUE;
    // 메모리 초과나서 input에 visit을 합침.
    // input값이 2일 때는 이미 지나간 곳.
    private static int[][] input;

    // 상, 하, 좌, 우
    private static int[] dy = {0, 0, 1, -1};
    private static int[] dx = {-1, 1, 0, 0};
    
    public static void main(String[] args) throws Exception {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer tk = new StringTokenizer(br.readLine(), " ");

        // Input 정리
        N = Integer.parseInt(tk.nextToken());
        M = Integer.parseInt(tk.nextToken());
        input = new int[N][M];
        
        for(int i = 0; i < N; i++) {
            String[] parse = br.readLine().split("");
            for(int j = 0; j < M; j++) {
                input[i][j] = Integer.parseInt(parse[j]);
            }
        }

        // dfs 실행. dfs는 지나간 자리 표시 안해도 됨.
        // visit[0][0] = 1;
        // dfs(0, 0, 0);

        // dfs가 시간초과남. bfs로 전환.
        bfs(0, 0);

        // 결과 출력
        // 마지막 칸에 도달하지 못한 경우
        if(result == Integer.MAX_VALUE) System.out.println("-1");
        // 마지막 칸에 도달 했을 경우 - 지나온 칸을 이야기 하는 것이니 첫째칸 포함해야함으로 +1로 출력
        else System.out.println(result+1);

    }

    // x좌표, y좌표
    public static void bfs(int x, int y) {

        // Queue 선언
        Queue<int[]> que = new ArrayDeque<int[]>();

        // 첫 좌표 Queue에 삽입, visit 표시, length 세기
        que.offer(new int[] {x, y});
        input[x][y] = 2;
        int length = 0;

        // bfs 시작
        while(!que.isEmpty()) {
            
            // 현재 단계의 que 갯수를 세서 그만큼 진행.
            // 현재 단계의 que를 전부 소모했음에도 여전히 도착점에 도달하지 못했다면 다음 단계로 보내기.
            int size = que.size();

            // size만큼 for문 돌리기.
            for(int i = 0; i < size; i++) {

                // que에서 1개 뽑아와서 진행.
                int[] cur = que.poll();

                // 만약 도착지점에 도달했을 경우
                if(cur[1] == M-1 && cur[0] == N-1) {
                    result = length;
                    return;
                }

                // 아니라면 사방탐색 진행
                for(int j = 0; j < 4; j++) {
                    
                    // 다음 좌표 작성
                    int tx = cur[0] + dx[j];
                    int ty = cur[1] + dy[j];

                    // 경계 체크, 지날 수 있는 길인지 체크, visit 했던 곳인지 체크
                    if(ty >= 0 && ty < M && tx >= 0 && tx < N && input[tx][ty] == 1) {
                        
                        // 디버깅을 위해 현재 visit 출력
                        //show();

                        // 방문 표시를 꺼내고 하는게 아니라 넣기 전에 해야 해당 칸을 중복해서 넣는 경우를 방지할 수 있음.
                        // input을 2로 변경
                        input[tx][ty] = 2;

                        // 다음 단계 진행 -> Que에 다음 좌표 제공.
                        que.offer(new int[] {tx, ty});

                    }
                }
            }

            // size만큼 다 돌렸음에도 도착점에 도달하지 못했으므로 해당 길이로는 도착점에 갈 수 없음
            // 따라서 +1 해주고 다음 단계로 넘어감
            length += 1;

        }

    }


    public static void show() {
        
        System.out.println("===================");
        for(int i = 0; i < N; i++) {
            System.out.println(Arrays.toString(input[i]));
        }
    }

    // x좌표, y좌표, 길이
    public static void dfs(int x, int y, int length) {

        // length가 result보다 길 경우 패스.
        if(length >= result) return;

        // x, y가 N-1, M-1에 도달함 -> 도착점
        if(x == N-1 && y == M-1) {
            if(length < result) result = length;
            return;
        }



        // 사방 탐색
        for(int i = 0; i < 4; i++){
            int ty = y + dy[i];
            int tx = x + dx[i];

            // visit 체크 + 경계 체크 + 벽 체크
            if(ty >= 0 && ty < M && tx >= 0 && tx < N && input[tx][ty] == 1) {
                
                // visit에 표시해주기.
                input[tx][ty] = 2;
                
                // 다음 탐색 시작.
                dfs(tx, ty, length+1);
                
                // visit 풀기.
                input[tx][ty] = 1;

            }

        }
    }

}

 

 

 

해설

 

 

  전형적인 bfs 문제입니다.

 

  습관적으로 dfs를 먼저 해보았지만 시간초과를 당해 bfs로 풀었습니다.

 

 

 

어려움 포인트

 

 

  그럼에도 주의해야할 점이 있다면 방문 표시를 해주는 위치입니다.

 

  제 코드를 보면 큐에 다음 좌표를 넣어주기 전에 방문 표시를 해주는데, 큐에서 뽑았을 때 방문 표시를 해주었을 경우 메모리 초과가 발생합니다. 방문 표시의 위치에 따라 1단계 더 큐에 넣고 넣지 않고가 결정되는데, 이 차이가 메모리 초과와 통과를 결정합니다.