C++로 그리드의 한쪽 끝에서 다른 쪽 끝까지 이동하는 데 필요한 최소 변경 횟수 구하기

x × y 크기의 그리드가 주어졌다고 가정해 보겠습니다. 이 그리드는 두 종류의 칸으로 이루어져 있는데, 하나는 접근할 수 없는 막힌 칸(blocked)이고 다른 하나는 자유롭게 이동할 수 있는 열린 칸(unblocked)입니다. 그리드는 2차원 배열로 표현되며, 막힌 칸은 '#', 열린 칸은 '.'으로 나타냅니다.

목표는 왼쪽 위 끝 칸인 (0, 0)에서 출발하여 오른쪽 아래 끝 칸인 (x−1, y−1)에 도달하는 것입니다. 사용할 수 있는 이동은 오직 두 가지뿐입니다. 현재 칸에서 오른쪽으로 한 칸 이동하거나 아래쪽으로 한 칸 이동하는 것입니다. 단, 열린 칸만 지나갈 수 있으며, 시작점과 도착점은 항상 열린 칸이라고 가정합니다.

만약 현재 상태로는 목적지에 도달할 수 없다면, 막힌 칸 하나를 열린 칸으로 바꾸는 연산을 수행할 수 있습니다. 이때 구해야 할 것은 출발점에서 도착점까지 이동하기 위해 수행해야 하는 최소 변경 횟수입니다.

예를 들어 입력이 x = 4, y = 4, grid = {"..#", "#.#.", "#.##", "###."}라면 출력은 1이 됩니다. 딱 한 번의 변경 연산만 수행하면 되는데, (2, 2) 위치의 칸을 막힌 상태에서 열린 상태로 바꾸면 (0, 0)에서 (3, 3)까지 이동할 수 있기 때문입니다.

해결 접근 방식

이 문제는 동적 계획법(Dynamic Programming)으로 해결할 수 있습니다. 핵심 아이디어는 각 칸에 도달하기 위해 필요한 최소 변경 횟수를 저장하는 2차원 배열 mat를 만드는 것입니다. 이동은 오른쪽과 아래쪽으로만 가능하므로, 배열을 왼쪽 위부터 차례대로 채워 나가면 됩니다.

이동 비용은 다음과 같이 정의됩니다. 다음 칸이 막혀 있고('#') 현재 칸이 열려 있다면('.'), 그 칸으로 이동할 때 비용 1이 추가되며, 그렇지 않으면 비용은 0입니다. 각 칸에는 도달 가능한 모든 경로 중 최소 비용을 기록하고, 마지막에 도착점의 값을 반환하면 됩니다.

알고리즘 단계

2차원 배열 mat를 정의한다
if grid[0][0] == '#'이면:
   mat[0][0] := 1
그렇지 않으면:
   mat[0][0] := 0
i := 0부터 i < x까지 1씩 증가시키며 반복:
   j := 0부터 j < y까지 1씩 증가시키며 반복:
      if i + 1 < x이면:
         mat[i + 1][j] = min(mat[i + 1][j], mat[i][j] + (grid[i + 1][j] == '#' AND grid[i][j] == '.'))
      if j + 1 < y이면:
         mat[i][j + 1] = min(mat[i][j + 1], mat[i][j] + (grid[i][j + 1] == '#' AND grid[i][j] == '.'))
return mat[x - 1][y - 1]

C++ 구현 예제

아래 구현 예제를 통해 더 잘 이해해 보겠습니다.

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

int solve(int x, int y, vector<string> grid){
    vector<vector<int>> mat(x, vector<int>(y, 100));
    if(grid[0][0] == '#')
       mat[0][0] = 1;
    else
       mat[0][0] = 0;
    for(int i = 0; i < x; i++){
       for(int j = 0; j < y; j++){
          if(i + 1 < x){
             mat[i + 1][j] = min(mat[i + 1][j], mat[i][j] + (grid[i + 1][j] == '#' && grid[i][j] == '.'));
          }
          if(j + 1 < y){
             mat[i][j + 1] = min(mat[i][j + 1], mat[i][j] + (grid[i][j + 1] == '#' && grid[i][j] == '.'));
          }
       }
    }
    return mat[x - 1][y - 1];
}
int main() {
    int x = 4, y = 4;
    vector<string> grid = {"..#", "#.#.", "#.##", "###."};
    cout << solve(x, y, grid);
    return 0;
}

입력

4, 4, {"..#", "#.#.", "#.##", "###."}