문제 정의
빈 공간과 벽으로 이루어진 미로 안에 공이 하나 놓여 있다고 가정해 보겠습니다. 공은 상, 하, 좌, 우 어느 방향으로든 굴러갈 수 있지만, 벽에 부딪히기 전까지는 절대 멈추지 않습니다. 공이 한 번 멈추면 그 자리에서 다음 방향을 새로 선택할 수 있습니다.
공의 시작 위치, 목적지, 그리고 미로 정보가 주어졌을 때, 공이 목적지 위에서 멈추게 되는 최단 거리를 구해야 합니다. 여기서 거리란 공이 지나간 빈 칸의 개수를 의미하며, 시작 위치는 제외하고 최종적으로 멈춘 지점까지 포함해서 셉니다. 어떤 방법을 써도 공을 목적지 위에 멈추게 할 수 없다면 -1을 반환해야 합니다.
미로는 2차원 배열로 표현됩니다. 1은 벽, 0은 빈 공간을 나타내며, 미로의 테두리는 모두 벽으로 둘러싸여 있습니다. 시작 위치와 목적지는 행(row)과 열(column) 인덱스로 주어집니다.
입력 예시
예를 들어 다음과 같은 5×5 미로가 입력으로 주어졌다고 합시다.
| 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 | 1 |
| 0 | 0 | 0 | 0 | 0 |
시작 위치는 (0, 4), 목적지는 (4, 4)입니다. 이때 출력값은 12가 됩니다. 한 가지 가능한 경로는 왼쪽 → 아래 → 왼쪽 → 아래 → 오른쪽 → 아래 → 오른쪽 순서로 굴러가는 것이며, 각 구간의 이동 거리를 모두 더하면 (1+1+3+1+2+2+2) = 12입니다.
접근 방법: BFS와 거리 갱신(Relaxation)
이 문제의 핵심은 일반적인 격자 탐색과 달리 공이 한 번 움직이면 벽에 닿을 때까지 멈추지 않는다는 점입니다. 따라서 한 칸씩 이동하는 대신, 공이 굴러서 멈추게 되는 지점을 하나의 노드로 보고 그래프 탐색을 수행해야 합니다.
각 지점까지의 최단 거리를 저장하는 2차원 배열 dist를 유지하고, 큐(queue)를 활용해 탐색을 진행합니다. 더 짧은 경로를 발견할 때마다 거리를 갱신하고 해당 지점을 다시 큐에 넣는 방식(거리 갱신, relaxation)을 사용하므로, 이동 거리가 매번 달라지는 이 문제에서도 정확한 최단 거리를 구할 수 있습니다.
알고리즘 단계
- n := 행 개수, m := 열 개수로 설정합니다.
- ret := 무한대(INF)로 초기화합니다.
- n × m 크기의 2차원 배열 dist를 정의하고 모든 값을 무한대로 초기화합니다.
- 큐 q를 정의하고 시작 위치를 삽입한 뒤, dist[start[0]][start[1]] := 0으로 설정합니다.
- q가 빌 때까지 다음을 반복합니다.
- curr := q의 첫 번째 요소를 꺼내고, x := curr[0], y := curr[1]로 설정합니다.
- (x, y)가 목적지와 같다면 ret := min(ret, dist[x][y])로 갱신합니다.
- currDist := dist[x][y]로 두고, 네 방향(아래, 위, 왼쪽, 오른쪽)에 대해 공이 굴러서 멈추는 지점(i)과 이동 거리(tempDist)를 계산합니다.
- currDist + tempDist가 dist[i][y](또는 dist[x][i])보다 작으면 값을 갱신하고 해당 지점을 큐에 삽입합니다.
- 탐색이 끝난 후 ret이 여전히 무한대라면 -1을, 그렇지 않으면 ret을 반환합니다.
C++ 구현 코드
아래 구현을 통해 동작 방식을 더 명확하게 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int shortestDistance(vector<vector<int>>& grid, vector<int>& start, vector<int>& destination) {
int n = grid.size();
int m = n ? grid[0].size() : 0;
int ret = INT_MAX;
vector<vector<int>> dist(n, vector<int>(m, INT_MAX));
queue<vector<int>> q;
q.push(start);
dist[start[0]][start[1]] = 0;
while (!q.empty()) {
vector<int> curr = q.front();
q.pop();
int x = curr[0];
int y = curr[1];
if (x == destination[0] && y == destination[1]) {
ret = min(ret, dist[x][y]);
}
int currDist = dist[x][y];
int tempDist = 0;
int i = x;
// 아래쪽으로 굴리기
while (i + 1 < n && !grid[i + 1][y]) {
i++;
tempDist++;
}
if (currDist + tempDist < dist[i][y]) {
dist[i][y] = currDist + tempDist;
q.push({i, y});
}
// 위쪽으로 굴리기
i = x;
tempDist = 0;
while (i - 1 >= 0 && !grid[i - 1][y]) {
tempDist++;
i--;
}
if (currDist + tempDist < dist[i][y]) {
dist[i][y] = currDist + tempDist;
q.push({i, y});
}
// 왼쪽으로 굴리기
i = y;
tempDist = 0;
while (i - 1 >= 0 && !grid[x][i - 1]) {
i--;
tempDist++;
}
if (currDist + tempDist < dist[x][i]) {
dist[x][i] = currDist + tempDist;
q.push({x, i});
}
// 오른쪽으로 굴리기
i = y;
tempDist = 0;
while (i + 1 < m && !grid[x][i + 1]) {
i++;
tempDist++;
}
if (currDist + tempDist < dist[x][i]) {
dist[x][i] = currDist + tempDist;
q.push({x, i});
}
}
return ret == INT_MAX ? -1 : ret;
}
};
int main() {
Solution ob;
vector<vector<int>> v = {{0,0,1,0,0},{0,0,0,0,0},{0,0,0,1,0},{1,1,0,1,1},{0,0,0,0,0}};
vector<int> v1 = {0, 4}, v2 = {4, 4};
cout << ob.shortestDistance(v, v1, v2);
return 0;
}
입력
{{0,0,1,0,0},{0,0,0,0,0},{0,0,0,1,0},{1,1,0,1,1},{0,0,0,0,0}}, {0,4}, {4,4}
출력
12
복잡도 분석
모든 칸은 더 짧은 경로가 발견될 때마다 다시 큐에 들어갈 수 있고, 한 번 처리할 때마다 한 방향으로 최대 max(n, m)칸을 굴러가며 확인하므로 시간 복잡도는 O(m·n·max(m, n))입니다. dist 배열과 큐가 차지하는 메모리를 고려하면 공간 복잡도는 O(m·n)입니다.