[백준] 2178번: 미로 탐색

💡문제 분석 요약

N x M 크기의 미로에서 (1, 1)에서 (N, M)까지 이동하는데 필요한 최소의 칸 수를 구하는 문제이다.

• 시간 제한: 1초
• 메모리 제한: 192MB

 

💡알고리즘 설계

• 줄의 개수 N, 칸의 개수 M 를 입력받고, (N, M)의 미로 정보를 입력받는다.
• BFS 메서드를 호출하여 미로를 탐색한다.
• BFS 메서드
  • `Queue<int[]>` 타입의 큐를 생성한다. (탐색할 좌표를 저장함)
  • 시작 위치 (1, 1)를 큐에 넣는다.
  • 큐가 빌 때까지:
    • 큐의 맨 앞의 값을 꺼낸다. ⇒ 현재 위치 (`cur`)
    • `cur`의 상하좌우를 탐색한다.
    • 탐색 위치 (x, y)가 미로의 범위에 속하고, 이동 가능한 경로 (`graph[x][y] = 1`)일 경우
      • 해당 위치를 큐에 넣는다.
      • 해당 위치를 방문 처리한다. (`graph[x][y] = 0`)
      • 해당 위치의 시간을 현재 위치의 시간 +1로 저장한다.
• (N, M) 위치의 시간을 반환한다.

 

💡코드

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

public class Main {
    static int N, M;
    static int[][] graph;
    static int[][] time;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    static void bfs() {
        Queue<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{1, 1});

        while(!q.isEmpty()) {
            int[] cur = q.poll();
            for(int i=0; i<4; i++) {
                int x = dx[i] + cur[0];
                int y = dy[i] + cur[1];
                if(x > 0 && x<=N && y > 0 && y <= M && graph[x][y] == 1) {
                    q.offer(new int[]{x, y});
                    graph[x][y] = 0;
                    time[x][y] = time[cur[0]][cur[1]] + 1;
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        N = Integer.parseInt(str[0]);
        M = Integer.parseInt(str[1]);

        graph = new int[N+1][M+1];
        time = new int[N+1][M+1];
        time[1][1] = 1;
        for(int i=1; i<=N; i++) {
            String info = br.readLine();
            for(int j=1; j<=M; j++) {
                graph[i][j] = Character.getNumericValue(info.charAt(j-1));
            }
        }

        bfs();
        System.out.println(time[N][M]);
    }
}

 

💡시간복잡도

줄의 개수가 N, 칸의 개수가 M일 때 시간복잡도는 $O(N*M)$ 이다.

 

💡 느낀점 or 기억할정보

이전에 풀었던 “유기농 배추”, “숨바꼭질” 문제와 비슷해서 쉽게 풀 수 있었다. 최소 이동 시간을 구할 때는 BFS 이용하기!