백준 2178번 미로탐색

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

2178번: 미로 탐색

 

 

분석

데이터의 최대 크기는 100이기 때문에 시간 제한은 별도로 생각할 필요없다.

BFS, DFS로 풀 수 있는 문제이고, BFS로 푸는 것이 더 쉽다.

이유는 BFS는 해당 깊이에서 갈 수 있는 노드 탐색을 마친 후 다음 깊이로 넘어가기 때문에 해당 깊이에서 (N,M)을 만나면 그 깊이가 바로 최솟값이 된다. 

DFS는 재귀로 내려갔다가 올라올때 깊이를 계산하는 것이 좀 까다롭다. 

 

슈도코드 (하루코딩 유튜브에서 가져옴)

 

코드

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

public class P1278_미로탐색 {
    static int[] dx = {0,1,0,-1};
    static int[] dy = {1,0,-1,0};   //상하좌우 탐색을 위한 변수
    static boolean[][] visited;        //방문기록 저장 배열
    static int[][] A;
    static int N, M;        //행, 열
    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());
        A = new int[N][M];
        visited = new boolean[N][M];
        for(int i = 0; i < N; i++){     //배열에 저장
            st = new StringTokenizer(br.readLine());
            String line = st.nextToken();
            for(int j = 0; j < M; j++){
                A[i][j] = Integer.parseInt(line.substring(j,j+1));
            }
        }
        BFS(0,0);
        System.out.println(A[N-1][M-1]);
    }

    private static void BFS(int i, int j) {
        Queue<int[]>queue = new LinkedList<>();
        queue.offer(new int[] {i,j});
        visited[i][j] = true;       //방문한 노드 표시
        while (!queue.isEmpty()){
            int now[] = queue.poll();
            for(int k = 0; k < 4; k++){     //상하좌우 탐색
                int x = now[0] + dx[k];
                int y = now[1] + dy[k];
                if(x>=0 && y>=0 && x<N && y<M) {    //좌표가 유효한지 검사(배열을 넘어가면 안됨)
                   if(A[x][y]!=0 && !visited[x][y]) {   //0이 아니고 이미 방문하지 않은 노드
                        visited[x][y] = true;
                        A[x][y] = A[now[0]][now[1]] + 1;    //배열 A에 현재 깊이 저장
                        queue.add(new int[] {x,y});
                    }
                }
            }
        }
    }

}

 

 

 

후기

유튜브 풀이 보고 풀었는데 사실 이해 안가는 부분도 있다. 일단 BufferedReader 사용법과 BFS의 정확한 개념 및 구현 방법을 다시 공부해야 할 것 같다..