14497번: 주난의 난

문제

N x M 크기의 2차원 맵에서 시작점(y1, x1)부터 도착점(y2, x2)까지 이동하려고 합니다. 맵의 각 칸은 빈 칸('0') 또는 벽으로 이루어져 있습니다. 빈 칸으로 이동할 때는 비용이 들지 않지만(가중치 0), 벽을 부수고 이동할 때는 1의 비용이 발생합니다(가중치 1). 상하좌우로 이동할 수 있을 때, 시작점에서 도착점까지 가기 위해 부숴야 하는 벽의 최소 개수(최소 이동 비용)를 구하는 프로그램을 작성하는 문제입니다.

• 입력: 맵의 세로 길이 n, 가로 길이 m, 시작점 좌표 y1, x1, 도착점 좌표 y2, x2, 그리고 맵의 상태 배열
• 출력: 도착점까지 이동하기 위해 부숴야 하는 벽의 최소 개수

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

풀이 1: 일반 Queue를 사용한 탐색 (오답)

빈 칸(0)으로 이동할 때는 비용이 0, 벽을 부술 때는 비용이 1이 추가되는 전형적인 최단 경로(가중치가 0과 1인 그래프) 문제입니다.

일반 큐를 사용하여 탐색을 진행했습니다. 하지만 일반 큐를 사용하는 BFS는 모든 간선의 가중치가 동일할 때만 '먼저 도달한 경로가 최단 경로'임을 보장합니다. 가중치가 0과 1이 섞여 있는 경우, 벽을 부수고 먼저 큐에 들어간 경로가, 벽을 부수지 않고 나중에 도달한 경로보다 먼저 처리되어 실제 최솟값을 갱신하지 못하는 치명적인 논리 오류(반례)가 발생하게 됩니다. 또한 원본 맵(a[ny][nx] = '0')을 직접 변경하면 다른 최적 경로 탐색에 악영향을 줄 수 있습니다.

코드 1 (기존 코드)

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

public class Main {
    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());

       st = new StringTokenizer(br.readLine());
       int y1 = Integer.parseInt(st.nextToken()) - 1;
       int x1 = Integer.parseInt(st.nextToken()) - 1;
       int y2 = Integer.parseInt(st.nextToken()) - 1;
       int x2 = Integer.parseInt(st.nextToken()) - 1;

       char[][] a = new char[n][m];
       for (int i = 0; i < n; i++) {
          a[i] = br.readLine().toCharArray();
       }

       Queue<int[]> q = new LinkedList<>();
       int[][] visited = new int[n][m];
       q.add(new int[] {y1, x1});
       visited[y1][x1] = 1;
       int[] dy = {-1, 1, 0, 0};
       int[] dx = {0, 0, -1, 1};

       while (!q.isEmpty()) {
          int[] cur = q.poll();
          int y = cur[0];
          int x = cur[1];

          if (y == y2 && x == x2)
             break;

          for (int i = 0; i < 4; i++) {
             int ny = y + dy[i];
             int nx = x + dx[i];

             if (ny < 0 || nx < 0 || ny >= n || nx >= m || visited[ny][nx] != 0)
                continue;
             if (a[ny][nx] == '0') {
                q.add(new int[] {ny, nx});
                visited[ny][nx] = visited[y][x];
             } else {
                q.add(new int[] {ny, nx});
                visited[ny][nx] = visited[y][x] + 1;
                a[ny][nx] = '0';
             }
          }
       }

       bw.write((visited[y2][x2] - 1) + "");

       bw.flush();
    }
}

풀이 2: ArrayDeque를 활용한 0-1 BFS 최적화 (정답)

가중치가 0과 1 두 가지만 존재할 때는 데크(Deque) 자료구조를 활용한 0-1 BFS 방식이 가장 빠르고 정확한 정석입니다.

• 핵심 원리:
  •  이동 비용이 0인 경우(빈 칸): 우선순위가 높으므로 큐의 맨 앞(addFirst)에 넣습니다.
  • 이동 비용이 1인 경우(벽 부수기): 우선순위가 낮으므로 큐의 맨 뒤(addLast)에 넣습니다.
• 이렇게 하면 항상 비용이 적은 경로를 먼저 탐색하게 되어 다익스트라(Dijkstra)와 동일한 최단 경로를 보장하면서도, 우선순위 큐(O(E log V))보다 빠른 O(V+E)의 시간 복잡도로 탐색할 수 있습니다.
• 원본 배열 수정 금지: 방문 처리는 오직 visited 배열의 최솟값 갱신을 통해서만 관리하여 원본 배열에 영향을 주지 않도록 안전하게 구현합니다.

코드 2

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

public class Main {
    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());

       st = new StringTokenizer(br.readLine());
       int y1 = Integer.parseInt(st.nextToken()) - 1;
       int x1 = Integer.parseInt(st.nextToken()) - 1;
       int y2 = Integer.parseInt(st.nextToken()) - 1;
       int x2 = Integer.parseInt(st.nextToken()) - 1;

       char[][] a = new char[n][m];
       for (int i = 0; i < n; i++) {
          a[i] = br.readLine().toCharArray();
       }

       // 0-1 BFS를 위해 성능이 우수한 ArrayDeque 사용
       Deque<int[]> dq = new ArrayDeque<>();
       
       // 최솟값 갱신을 위해 visited 배열을 최대값으로 초기화
       int[][] visited = new int[n][m];
       for (int i = 0; i < n; i++) {
           Arrays.fill(visited[i], Integer.MAX_VALUE);
       }
       
       // 시작점 처리
       dq.addFirst(new int[] {y1, x1});
       visited[y1][x1] = 0; // 시작점의 벽 부수기 비용은 0
       
       int[] dy = {-1, 1, 0, 0};
       int[] dx = {0, 0, -1, 1};

       while (!dq.isEmpty()) {
          int[] cur = dq.pollFirst();
          int y = cur[0];
          int x = cur[1];

          // 목적지 도달 시 종료
          if (y == y2 && x == x2) {
             break;
          }

          for (int i = 0; i < 4; i++) {
             int ny = y + dy[i];
             int nx = x + dx[i];

             // 범위 체크
             if (ny < 0 || nx < 0 || ny >= n || nx >= m) {
                 continue;
             }
             
             // 다음 칸이 빈 칸(0)인 경우: 비용 0 추가, 큐의 맨 앞에 삽입
             if (a[ny][nx] == '0') {
                 if (visited[ny][nx] > visited[y][x]) {
                     visited[ny][nx] = visited[y][x];
                     dq.addFirst(new int[] {ny, nx});
                 }
             } 
             // 다음 칸이 벽(1 등)인 경우: 비용 1 추가, 큐의 맨 뒤에 삽입
             else {
                 if (visited[ny][nx] > visited[y][x] + 1) {
                     visited[ny][nx] = visited[y][x] + 1;
                     dq.addLast(new int[] {ny, nx});
                 }
             }
          }
       }

       // 최단 비용 출력
       bw.write(visited[y2][x2] + "");

       bw.flush();
    }
}

알고리즘 분류

그래프 탐색 (Graph Traversal), 너비 우선 탐색 (BFS), 0-1 BFS, 데크 (Deque)