문제 설명
m × n 크기의 격자(grid)가 주어지며, 각 칸은 0 또는 1의 값만 가집니다. 여기서 0은 빈 칸, 1은 막혀 있는 칸(장애물)을 의미합니다. 한 번의 이동으로 상, 하, 좌, 우 방향의 인접한 빈 칸으로 움직일 수 있습니다.
목표는 왼쪽 위 모서리 칸 (0, 0)에서 출발해 오른쪽 아래 모서리 칸 (m-1, n-1)에 도달할 때까지 걸리는 최소 이동 횟수를 구하는 것입니다. 단, 이동 과정에서 최대 k개의 장애물을 제거할 수 있습니다. 어떤 방법으로도 목적지에 도달할 수 없다면 -1을 반환해야 합니다.
입력 예시
| 0 | 0 | 0 |
| 1 | 1 | 0 |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 0 | 0 | 0 |
k = 1일 때 정답은 6입니다. 장애물을 하나도 제거하지 않는 경우 최단 경로 길이는 10이지만, 위치 (3, 2)의 장애물을 하나 제거하면 경로를 6으로 줄일 수 있습니다. 실제 경로는 다음과 같습니다.
(0,0) → (0,1) → (0,2) → (1,2) → (2,2) → (3,2) → (4,2)
풀이 접근 방법
이 문제는 상태 공간에 '남은 장애물 제거 횟수'를 추가한 BFS(너비 우선 탐색)로 해결할 수 있습니다. 일반적인 그리드 최단 경로 문제와 달리, 같은 칸이라도 남은 제거 횟수(k)에 따라 상태가 서로 다르므로 3차원 방문 배열(dp[x][y][k])을 사용해 중복 탐색을 방지하는 것이 핵심입니다.
구체적인 풀이 절차는 다음과 같습니다.
- 좌표 (x, y)가 격자 범위(r × c) 안에 있는지 검사하는 ok() 함수를 정의합니다.
- dp[50][50][2000] 형태의 3차원 배열을 선언해 각 상태별 최단 거리를 저장합니다.
- 현재 좌표(x, y), 남은 제거 횟수(k), 이동 거리(length)를 담는 Data 구조체를 정의합니다.
- 메인 로직(shortestPath 함수)은 다음 순서로 동작합니다.
- dp 배열을 무한대(INT_MAX)로 초기화합니다.
- r은 행 개수, c는 열 개수로 설정합니다.
- BFS용 큐 q를 만들고, (x = 0, y = 0, k, length = 0)인 루트 노드를 삽입합니다.
- 큐가 빌 때까지 다음을 반복합니다.
- 큐의 맨 앞 노드를 꺼내 x, y, k, length 값을 읽습니다.
- 현재 위치가 (r-1, c-1)이면 length를 반환합니다.
- length를 1 증가시킨 뒤, 네 방향(상하좌우)에 대해 탐색합니다.
- 다음 좌표(nx, ny)가 목적지라면 즉시 length를 반환합니다.
- 다음 칸이 빈 칸(0)이고 length가 dp[nx][ny][k]보다 작으면, 새 노드를 큐에 삽입하고 dp 값을 갱신합니다.
- 다음 칸이 장애물(1)이면서 k > 0이고 length가 dp[nx][ny][k]보다 작으면, 제거 횟수를 1 소모한 상태(k-1)로 노드를 큐에 삽입하고 dp 값을 갱신합니다.
- 큐가 소진될 때까지 목적지에 도달하지 못하면 -1을 반환합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
int dir [4][2]={{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int dp[50][50][2000];
struct Data{
int x, y, k, length;
Data(int a, int b, int c, int d){
x = a;
y = b;
k = c;
length = d;
}
};
class Solution {
public:
void pre(){
for (int i = 0; i < 50; i++) {
for (int j = 0; j < 50; j++) {
for (int k = 0; k < 2000; k++) {
dp[i][j][k] = INT_MAX;
}
}
}
}
bool ok(int x, int y, int r, int c){
return (x < r && y < c && x >= 0 && y >= 0);
}
int shortestPath(vector<vector<int> >& grid, int k){
pre();
int r = grid.size();
int c = grid[0].size();
queue<Data> q;
Data root(0, 0, k, 0);
q.push(root);
while (!q.empty()) {
Data node = q.front();
q.pop();
int x = node.x;
int y = node.y;
int k = node.k;
int length = node.length;
if (x == r - 1 && y == c - 1)
return length;
length++;
for (int i = 0; i < 4; i++) {
int nx = x + dir[i][0];
int ny = y + dir[i][1];
if (nx == r - 1 && ny == c - 1)
return length;
if (ok(nx, ny, r, c)) {
if (grid[nx][ny] == 0) {
if (length < dp[nx][ny][k]) {
q.push(Data(nx, ny, k, length));
dp[nx][ny][k] = length;
}
}
else {
if (k > 0 && length < dp[nx][ny][k]) {
q.push(Data(nx, ny, k - 1, length));
dp[nx][ny][k] = length;
}
}
}
}
}
return -1;
}
};
main(){
Solution ob;
vector<vector<int>> v = {{0,0,0},{1,1,0},{0,0,0},{0,1,1},
{0,0,0}};
cout << (ob.shortestPath(v, 1));
}입력
{{0,0,0},{1,1,0},{0,0,0},{0,1,1},{0,0,0}}출력
6
복잡도 분석
각 칸은 남은 제거 횟수별로 최대 한 번씩만 큐에 들어가므로, 시간 복잡도는 O(m × n × k)입니다. 공간 복잡도 역시 3차원 dp 배열을 사용하기 때문에 O(m × n × k)입니다. 이처럼 BFS에 상태 차원을 하나 더 추가하는 기법은 '제한된 자원을 사용할 수 있는 경로 탐색' 유형의 문제에 널리 활용됩니다.