문제 소개
빈 칸과 벽으로 이루어진 미로 안에 공 하나가 놓여 있다고 가정해 보겠습니다. 공은 위(u), 아래(d), 왼쪽(l), 오른쪽(r) 네 방향으로 굴러갈 수 있으며, 한 번 굴러가기 시작하면 벽에 부딪힐 때까지 멈추지 않습니다. 공이 멈춘 지점에서는 다음 방향을 다시 선택할 수 있습니다. 또한 미로에는 구멍(hole)이 하나 존재하는데, 공이 구멍 위를 지나가면 그대로 구멍 속으로 떨어집니다.
공의 시작 위치, 구멍의 위치, 그리고 미로 정보가 주어졌을 때, 공이 구멍에 떨어질 수 있는 최단 거리의 이동 경로를 찾아야 합니다. 여기서 거리란 시작 지점(제외)부터 구멍(포함)까지 공이 지나간 빈 칸의 개수를 의미합니다.
결과는 'u', 'd', 'l', 'r' 문자로 구성된 이동 경로 문자열로 반환합니다. 최단 경로가 여러 개 존재할 수 있으므로, 그중 사전순(lexicographically)으로 가장 작은 경로를 출력해야 합니다. 만약 공이 구멍에 도달할 수 없다면 "impossible"을 출력합니다.
미로는 2차원 이진 행렬로 표현되며, 1은 벽, 0은 빈 칸을 뜻합니다. 공과 구멍의 위치는 각각 행(row)과 열(column) 인덱스로 주어집니다.
예시
예를 들어 다음과 같은 입력이 주어졌다고 해봅시다.
이때 출력은 'lul'입니다. 왼쪽으로 굴린 뒤 위로, 다시 왼쪽으로 굴린다는 의미입니다. 'ul'(위 → 왼쪽) 역시 가능한 경로인데, 두 경로 모두 길이는 6으로 동일하지만 'ul'은 'lul'보다 사전순으로 크기 때문에 정답에서 제외됩니다.
접근 방법
이 문제는 우선순위 큐(priority queue)를 활용한 다익스트라(Dijkstra) 알고리즘으로 해결할 수 있습니다. 거리가 가장 짧은 상태를 먼저 처리하고, 거리가 같다면 경로 문자열이 사전순으로 앞서는 상태를 먼저 처리하도록 비교자(comparator)를 구성하는 것이 핵심입니다.
- 거리(dist), 경로 문자열(d), 좌표(x, y)를 담는 Data 구조체를 정의합니다.
- 4방향 이동 배열 dir := {{1, 0}, {0, -1}, {0, 1}, {-1, 0}}을 선언합니다.
- 각 방향에 대응하는 문자 배열 dirst := {'d', 'l', 'r', 'u'}를 선언합니다.
- 두 좌표가 동일한지 검사하는 ok() 함수를 정의합니다.
알고리즘 단계
- n := 미로의 행 크기, m := n이 0이 아니면 미로의 열 크기, 아니면 0으로 설정합니다.
- 우선순위 큐 pq를 생성하고, 초기 상태 (거리 0, 공의 좌표, 빈 문자열 "")를 삽입합니다.
- n × m 크기의 visited 2차원 배열을 준비합니다.
- pq가 빌 때까지 다음 과정을 반복합니다.
- pq의 최상단 원소를 curr로 꺼내 x, y, dist, d 값을 추출합니다.
- ok(x, y, hole[0], hole[1])가 참이라면, 즉 현재 위치가 구멍이라면 d를 반환합니다.
- visited[x][y]를 true로 표시하고 pq에서 해당 원소를 제거합니다.
- k를 0부터 3까지 증가시키며 4방향에 대해 다음을 수행합니다.
- nx := x, ny := y, tempDist := 0으로 초기화합니다.
- 다음 칸이 미로 범위 안에 있고 벽이 아니라면 공을 계속 굴립니다. nx와 ny를 이동 방향만큼 갱신하고 tempDist를 1씩 증가시킵니다.
- 굴러가는 도중 현재 위치가 구멍이라면 내부 반복문을 종료합니다.
- visited[nx][ny]가 false라면 새로운 Data(dist + tempDist, nx, ny, d + dirst[k])를 pq에 삽입합니다.
- 큐가 비었는데도 구멍에 도달하지 못했다면 "impossible"을 반환합니다.
구현 예시
아래 코드를 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
int dir[4][2] = {{1, 0}, {0, -1}, {0, 1}, {-1, 0}};
char dirst[4] = {'d', 'l', 'r', 'u'};
class Solution {
public:
struct Data {
int dist;
string d;
int x, y;
Data(int a, int b, int c, string s) {
d = s;
dist = a;
x = b;
y = c;
}
};
struct Comparator {
bool operator()(Data a, Data b) {
return a.dist != b.dist ? !(a.dist < b.dist) : !(a.d < b.d);
}
};
bool ok(int x1, int y1, int x2, int y2) { return x1 == x2 && y1 == y2; }
string findShortestWay(vector<vector<int>> &maze, vector<int>&ball,
vector<int> &hole) {
int n = maze.size();
int m = n ? maze[0].size() : 0;
priority_queue<vector<Data>, vector<Data>, Comparator> pq;
pq.push(Data(0, ball[0], ball[1], ""));
vector<vector<bool>> visited(n, vector<bool>(m));
while (!pq.empty()) {
Data curr = pq.top();
int x = curr.x;
int y = curr.y;
int dist = curr.dist;
string d = curr.d;
if (ok(x, y, hole[0], hole[1])) {
return d;
}
visited[x][y] = true;
pq.pop();
for (int k = 0; k < 4; k++) {
int nx = x;
int ny = y;
int tempDist = 0;
while (nx + dir[k][0] < n && nx + dir[k][0] >= 0 && ny + dir[k][1] < m && ny + dir[k][1] >= 0 && !maze[nx + dir[k][0]][ny + dir[k][1]]) {
nx += dir[k][0];
ny += dir[k][1];
tempDist++;
if (ok(nx, ny, hole[0], hole[1]))
break;
}
if (!visited[nx][ny]) {
pq.push(Data(dist + tempDist, nx, ny, d + dirst[k]));
}
}
}
return "impossible";
}
};
main() {
Solution ob;
vector<vector<int>> v = {
{0, 0, 0, 0, 0},
{1, 1, 0, 0, 1},
{0, 0, 0, 0, 0},
{0, 1, 0, 0, 1},
{0, 1, 0, 0, 0}};
vector<int> v1 = {4, 3}, v2 = {0, 1};
cout << (ob.findShortestWay(v, v1, v2));
}입력
vector<vector<int>> v = {{0, 0, 0, 0, 0},
{1, 1, 0, 0, 1},
{0, 0, 0, 0, 0},
{0, 1, 0, 0, 1},
{0, 1, 0, 0, 0}};
vector<int> v1 = {4, 3}, v2 = {0, 1};출력
lul