목표 지점에 도달하기 위한 최소 펀치 횟수를 찾는 C++ 프로그램

행이 H개, 열이 W개인 행렬이 있다고 가정해 보겠습니다. 각 칸에는 '.' 또는 '#' 문자가 들어 있는데, 점('.')은 통과할 수 있는 공간을, 샵('#')은 막혀 있는 블록을 의미합니다. 아말(Amal)은 자신의 집에서 시장으로 이동해야 하며, 집은 행렬의 왼쪽 맨 위(좌상단) 칸에, 시장은 오른쪽 맨 아래(우하단) 칸에 위치해 있습니다.

아말은 상하좌우 인접한 칸으로 한 칸씩 이동할 수 있으며, 이동 대상 칸은 반드시 통과 가능한 칸이어야 합니다. 마을 밖으로 나갈 수 없고, 막힌 칸('#')에 들어가는 것도 불가능합니다. 다만 그의 신체 능력 덕분에 한 번의 펀치로 자신이 선택한 2×2 크기의 정사각형 영역에 있는 모든 블록을 파괴하여 해당 칸들을 통과 가능하게 만들 수 있습니다. 우리가 구해야 할 것은 아말이 시장에 도달하기 위해 필요한 최소 펀치 횟수입니다.

입력 예시

예를 들어 입력이 다음과 같다고 해보겠습니다.

이 경우 출력값은 1이 됩니다. 아래와 같이 표시된 칸들의 블록을 한 번의 펀치로 부수면 경로가 열리기 때문입니다.

풀이 방법 (0-1 BFS)

이 문제는 이동 비용이 0 또는 1로만 구성되어 있으므로 0-1 BFS(덱을 활용한 너비 우선 탐색) 기법으로 효율적으로 해결할 수 있습니다. 빈 칸('.')으로 이동할 때는 비용이 0이므로 덱의 앞(front)에 삽입하고, 블록('#')을 만나 펀치를 사용할 때는 비용이 1이므로 덱의 뒤(back)에 삽입하는 방식입니다.

핵심 아이디어는 다음과 같습니다.

• 빈 칸으로 이동하면 펀치 횟수가 증가하지 않으므로, 현재 칸의 거리 값을 그대로 유지합니다.
• 블록 칸에 인접해 있다면, 그 블록 주변 3×3 범위 내의 칸들은 하나의 펀치로 함께 열 수 있습니다. 따라서 펀치 횟수를 1 증가시켜 거리 값을 갱신합니다.
• 거리 값이 갱신될 때마다 해당 칸을 덱에 넣어 탐색을 계속 진행합니다.

구체적인 알고리즘 단계는 다음과 같습니다.

n := 행렬의 행 개수
m := 행렬의 열 개수
(n + 1) x (m + 1) 크기의 2차원 배열 dist 정의
deque dq 정의
(0, 0)을 dq의 앞에 삽입
dist[0][0] := 0
dq가 비어 있지 않은 동안 반복:
    v := dq의 첫 번째 원소
    dq에서 앞 원소 제거
    i가 0부터 4 미만일 때까지 반복:
        x := dx[i] + v[0]
        y := dy[i] + v[1]
        만약 x >= 0 이고 x < n 이고 y >= 0 이고 y < m 이면:
            만약 matrix[x][y]가 '.'이라면:
                dist[x][y] > dist[v[0]][v[1]] 이면:
                    dist[x][y] := dist[v[0]][v[1]]
                    {x, y} 쌍을 dq의 앞에 삽입
            아니라면:
                p가 x - 1부터 x + 1까지 반복:
                    q가 y - 1부터 y + 1까지 반복:
                        p, q가 범위 안이면:
                            dist[p][q] > dist[v[0]][v[1]] + 1 이면:
                                dist[p][q] := dist[v[0]][v[1]] + 1
                                {p, q} 쌍을 dq의 뒤에 삽입
dist[n - 1][m - 1] 반환

C++ 구현 예제

아래 코드를 통해 더 잘 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;

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

int solve(vector<vector<char>> matrix){
   int n = matrix.size();
   int m = matrix[0].size();
   vector<vector<int>> dist(n + 1, vector<int>(m + 1, 1e9));
   deque<array<int, 2>> dq;
   dq.push_front({ 0, 0 });
   dist[0][0] = 0;
   while (!dq.empty()){
      auto v = dq.front();
      dq.pop_front();
      for (int i = 0; i < 4; i++){
         int x = dx[i] + v[0], y = dy[i] + v[1];
         if (x >= 0 && x < n && y >= 0 && y < m){
            if (matrix[x][y] == '.'){
               if (dist[x][y] > dist[v[0]][v[1]]){
                  dist[x][y] = dist[v[0]][v[1]];
                  dq.push_front({ x, y });
               }
            } else{
               for (int p = x - 1; p <= x + 1; p++){
                  for (int q = y - 1; q <= y + 1; q++){
                     if (p >= 0 && p < n && q >= 0 && q < m){
                        if (dist[p][q] > dist[v[0]][v[1]] + 1){
                           dist[p][q] = dist[v[0]][v[1]] + 1;
                           dq.push_back({ p, q });
                        }
                     }
                  }
               }
            }
         }
      }
   }
   return dist[n - 1][m - 1];
}
int main(){
   vector<vector<char>> matrix = { { '.', '.', '#', '.', '.' }, { '#', '.', '#', '.', '#' }, { '#', '#', '.', '#', '#' }, { '#', '.', '#', '.', '#' }, { '.', '.', '#', '.', '.' } };
   cout << solve(matrix) << endl;
}

입력

{ { '.', '.', '#', '.', '.' }, { '#', '.', '#', '.', '#' },
{ '#', '#', '.', '#', '#' }, { '#', '.', '#', '.', '#' }, {
'.', '.', '#', '.', '.' } }

출력

1

마무리

이 알고리즘은 일반 BFS처럼 각 칸을 최대 몇 번씩만 방문하므로 시간 복잡도는 O(H×W)에 가깝게 동작하며, 격자가 커져도 효율적으로 처리할 수 있습니다. 0-1 BFS는 가중치가 0과 1뿐인 최단 경로 문제에서 다익스트라 알고리즘을 대체할 수 있는 강력한 기법이므로, 이번 예제를 통해 원리를 꼭 익혀 두시기 바랍니다.