[백준 2206] 벽 부수고 이동하기 (C#, C++) - soo:bak

문제 링크

2206번 - 벽 부수고 이동하기

설명

격자의 각 칸이 빈 칸 또는 벽으로 이루어져 있고, 시작점에서 도착점까지 이동하는 최단 경로를 구하는 문제입니다.

이동 중 벽을 최대 한 번까지 부수고 지나갈 수 있으며, 상하좌우로만 이동할 수 있습니다.

최단 거리는 지나는 칸의 개수로 측정되며, 시작 칸과 도착 칸을 모두 포함합니다.

도착할 수 없는 경우 -1을 출력합니다.

접근법

일반적인 최단 경로 문제와 달리 벽을 한 번 부술 수 있으므로,

같은 위치라도 “벽을 아직 부수지 않은 상태”와 “이미 벽을 부순 상태”를 구분해야 합니다.

예를 들어 어떤 칸에 벽을 부수지 않고 도착한 경우와 벽을 부수고 도착한 경우는 이후 경로가 달라질 수 있으므로 별도로 관리해야 합니다.

모든 칸의 이동 비용이 1로 동일하므로 BFS를 사용하면 가장 먼저 도착점에 도달하는 경로가 최단 경로임이 보장됩니다.

각 위치마다 두 가지 상태(벽을 부수지 않은 상태, 부순 상태)를 저장하는 3차원 방문 배열을 사용합니다.

시작점에서 벽을 부수지 않은 상태로 탐색을 시작하여, 상하좌우 네 방향으로 확장합니다.

예를 들어 다음과 같은 3×3 격자가 있다고 가정합니다 (0은 빈 칸, 1은 벽):

0 1 0
0 1 0
0 0 0

왼쪽 위 (0,0)에서 오른쪽 아래 (2,2)로 이동할 때, 벽을 부수지 않으면 아래→아래→오른쪽→오른쪽으로 5칸을 지나야 하지만, 중간 벽 하나를 부수면 오른쪽→아래→오른쪽으로 3칸만에 도착할 수 있습니다.

다음 칸이 빈 칸이면 벽을 사용하지 않으므로 현재 상태를 유지하며 이동합니다.

다음 칸이 벽이고 아직 벽을 부수지 않았다면 벽 부수기 기회를 사용하여 부순 상태로 변경합니다.

이미 벽을 부순 상태에서는 더 이상 벽을 부술 수 없으므로 벽을 만나면 이동할 수 없습니다.

BFS는 최단 거리를 보장하므로, 도착점에 처음 도달했을 때의 거리가 답이 됩니다.

도착점에 도달하지 못하고 탐색이 끝나면 -1을 출력합니다.

각 위치마다 두 상태를 관리하므로 시간 복잡도는 O(N×M×2)이며, N과 M이 최대 1,000일 때 충분히 처리할 수 있습니다.

---

Code

C#

using System;
using System.Collections.Generic;

namespace Solution {
  class Program {
    static readonly int[] dy = { -1, 1, 0, 0 };
    static readonly int[] dx = { 0, 0, -1, 1 };

    static void Main(string[] args) {
      var first = Console.ReadLine()!.Split();
      var n = int.Parse(first[0]);
      var m = int.Parse(first[1]);

      var grid = new int[n][];

      for (var i = 0; i < n; i++) {
        var line = Console.ReadLine()!;
        grid[i] = new int[m];
        for (var j = 0; j < m; j++) grid[i][j] = line[j] - '0';
      }

      var dist = new int[n, m, 2];
      var q = new Queue<(int y, int x, int broken)>();

      dist[0, 0, 0] = 1;
      q.Enqueue((0, 0, 0));

      var answer = -1;

      while (q.Count > 0) {
        var cur = q.Dequeue();
        var curDist = dist[cur.y, cur.x, cur.broken];

        if (cur.y == n - 1 && cur.x == m - 1) { answer = curDist; break; }

        for (var dir = 0; dir < 4; dir++) {
          var ny = cur.y + dy[dir];
          var nx = cur.x + dx[dir];

          if (ny < 0 || ny >= n || nx < 0 || nx >= m) continue;

          if (grid[ny][nx] == 0 && dist[ny, nx, cur.broken] == 0) {
            dist[ny, nx, cur.broken] = curDist + 1;
            q.Enqueue((ny, nx, cur.broken));
          }

          if (grid[ny][nx] == 1 && cur.broken == 0 && dist[ny, nx, 1] == 0) {
            dist[ny, nx, 1] = curDist + 1;
            q.Enqueue((ny, nx, 1));
          }
        }
      }

      Console.WriteLine(answer);
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;
typedef vector<string> vs;

struct Node {
  int y, x, broken;
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m; cin >> n >> m;
  vs grid(n);

  for (int i = 0; i < n; i++) cin >> grid[i];

  vector<vector<array<int, 2>>> dist(n, vector<array<int, 2>>(m, {0, 0}));
  queue<Node> q;

  dist[0][0][0] = 1;
  q.push({0, 0, 0});

  const int dy[4] = {-1, 1, 0, 0};
  const int dx[4] = {0, 0, -1, 1};
  int answer = -1;

  while (!q.empty()) {
    Node cur = q.front();
    q.pop();
    int curDist = dist[cur.y][cur.x][cur.broken];

    if (cur.y == n - 1 && cur.x == m - 1) { answer = curDist; break; }

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

      if (ny < 0 || ny >= n || nx < 0 || nx >= m) continue;

      if (grid[ny][nx] == '0' && dist[ny][nx][cur.broken] == 0) {
        dist[ny][nx][cur.broken] = curDist + 1;
        q.push({ny, nx, cur.broken});
      }

      if (grid[ny][nx] == '1' && cur.broken == 0 && dist[ny][nx][1] == 0) {
        dist[ny][nx][1] = curDist + 1;
        q.push({ny, nx, 1});
      }
    }
  }

  cout << answer << "\n";

  return 0;
}