2178번: 미로 탐색

문제

N×M 크기의 배열로 표현되는 미로가 있습니다. 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타냅니다. (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 문제입니다. 한 칸에서 다른 칸으로 이동할 때에는 서로 인접한 칸으로만 이동할 수 있습니다. (칸을 셀 때에는 시작 위치와 도착 위치도 포함합니다.)

• 입력: 첫째 줄에 두 정수 N, M (2 ≤ N, M ≤ 100)이 주어집니다. 다음 N개의 줄에는 M개의 정수로 미로가 주어집니다. 각각의 수들은 붙어서 입력으로 주어집니다.
• 출력: 첫째 줄에 지나야 하는 최소의 칸 수를 출력합니다.

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

풀이

가중치가 동일한(모든 칸의 이동 거리가 1인) 2차원 격자에서 출발점으로부터 도착점까지의 최단 경로를 찾는 문제이므로, 너비 우선 탐색(BFS)을 사용하는 가장 대표적인 유형입니다.

1. 상태 관리 클래스 및 큐 초기화: 좌표 (y, x)를 담기 위해 Node 클래스를 생성하고, BFS 탐색을 위한 큐(Queue)를 선언합니다. 시작점인 (0, 0)을 큐에 넣고 방문 처리를 합니다.
2. 이동 거리 누적 배열 (visited): visited 배열을 단순한 boolean 타입의 방문 여부 체크용이 아닌 int 타입으로 선언합니다. 이를 통해 방문 여부(0이면 미방문, 0이 아니면 방문)를 확인함과 동시에, 시작점으로부터 해당 칸까지 이동하는 데 걸린 최소 칸 수를 누적하여 기록할 수 있습니다.
   • 시작점의 거리를 1로 초기화합니다: visited[0][0] = 1;
   • 다음 칸으로 이동할 때 이전 칸의 거리에서 1을 더해줍니다: visited[ny][nx] = visited[node.y][node.x] + 1;
3. 상하좌우 탐색 (BFS): 큐에서 좌표를 하나씩 꺼내어 상하좌우 4방향을 탐색합니다.
   • 미로의 범위를 벗어나지 않고 (ny >= 0 && nx >= 0 && ny < n && nx < m)
   • 벽이 아니며 (a[ny][nx] != '0')
   • 아직 방문하지 않은 칸 (visited[ny][nx] == 0) 위 조건을 모두 만족하는 칸만 큐에 추가하여 탐색을 이어나갑니다.
4. 결과 출력: BFS 탐색이 모두 끝나면 목적지인 (N-1, M-1) 좌표의 visited 배열 값을 출력합니다. 도착점의 값이 곧 시작점부터 도착점까지의 최단 거리가 됩니다.

코드

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

public class Main {
    // 상하좌우 탐색을 위한 델타 배열
    static int[] dy = {-1, 0, 1, 0};
    static int[] dx = {0, 1, 0, -1};

    public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

       StringTokenizer st = new StringTokenizer(br.readLine());
       int n = Integer.parseInt(st.nextToken());
       int m = Integer.parseInt(st.nextToken());
       
       // 미로 배열 입력 처리
       char[][] a = new char[n][m];
       for (int i = 0; i < n; i++) {
          a[i] = br.readLine().toCharArray();
       }

       // 방문 여부 및 누적 거리를 저장할 배열
       int[][] visited = new int[n][m];
       Queue<Node> q = new LinkedList<>();
       
       // 시작점 (0, 0) 초기화
       q.add(new Node(0, 0));
       visited[0][0] = 1; // 시작 위치도 칸 수에 포함하므로 1부터 시작

       // 너비 우선 탐색 (BFS) 진행
       while (!q.isEmpty()) {
          Node node = q.poll();
          
          // 상하좌우 4방향 탐색
          for (int i = 0; i < 4; i++) {
             int ny = node.y + dy[i];
             int nx = node.x + dx[i];
             
             // 1. 미로 범위를 벗어나면 무시
             if (ny < 0 || nx < 0 || ny >= n || nx >= m)
                continue;
             // 2. 벽('0')이거나 이미 방문한 칸이면 무시
             if (a[ny][nx] == '0' || visited[ny][nx] != 0)
                continue;
             
             // 이동할 수 있는 칸이면 큐에 추가하고, 이전 칸의 이동 거리 + 1 기록
             q.add(new Node(ny, nx));
             visited[ny][nx] = visited[node.y][node.x] + 1;
          }
       }

       // 도착점(우측 하단 끝)에 기록된 최소 이동 칸 수 출력
       bw.write(visited[n - 1][m - 1] + "");

       bw.flush();
       bw.close();
       br.close();
    }

    // 좌표 정보를 큐에 담기 위한 내부 클래스
    static class Node {
       int y, x;

       public Node(int y, int x) {
          this.y = y;
          this.x = x;
       }
    }
}

알고리즘 분류

그래프 탐색 (Graph Traversal), 너비 우선 탐색 (BFS)