h × w 크기의 격자(grid)가 있다고 가정해 봅시다. 이 격자는 'initGrid'라는 2차원 배열로 표현되며, 각 셀은 '#' 또는 '.' 문자로 이루어져 있습니다. '#'은 해당 칸에 장애물이 있음을 의미하고, '.'은 지나갈 수 있는 통로를 의미합니다.
로봇은 행 번호 x, 열 번호 y에 해당하는 셀 'c' 위에 놓여 있으며, 행 번호 p, 열 번호 q에 해당하는 다른 셀 'd'로 이동해야 합니다. 두 좌표 c와 d는 정수 쌍(pair) 형태로 주어집니다.
로봇의 이동 규칙
걷기: 현재 셀에서 상하좌우로 인접한 셀이라면 자유롭게 걸어서 이동할 수 있습니다.
점프: 현재 위치를 중심으로 하는 5×5 영역 안의 임의의 셀로 점프할 수 있습니다.
제약 조건: 이동하려는 셀에 장애물('#')이 없어야 하며, 격자 밖으로 나갈 수 없습니다.
구해야 할 값은 시작 셀 c에서 목적지 셀 d까지 이동하는 데 필요한 최소 점프 횟수입니다.
예를 들어 입력이 h = 4, w = 4, c = {2, 1}, d = {4, 4}, initGrid = {"#...", ".##.", "...#", "..#."}라면 출력은 1입니다. 로봇은 목적지에 도달하기 위해 딱 한 번의 점프만 하면 됩니다.
해결 접근 방법: 0-1 BFS
이 문제는 0-1 BFS(너비 우선 탐색) 기법으로 효율적으로 풀 수 있습니다. 걷기는 비용 0, 점프는 비용 1인 간선으로 볼 수 있으므로, 덱(deque)을 활용하면 가중치가 0 또는 1인 그래프의 최단 거리를 일반 다익스트라보다 간결하고 빠르게 계산할 수 있습니다.
알고리즘의 핵심 아이디어는 다음과 같습니다.
- 현재 셀을 중심으로 x, y 방향으로 −2부터 +2까지의 모든 오프셋을 조사합니다.
- 맨해튼 거리(|diffx| + |diffy|)가 1 이하이면 걷기(비용 0), 그보다 크면 점프(비용 1)로 간주합니다.
- 비용 0 이동은 덱의 앞(front)에, 비용 1 이동은 덱의 뒤(back)에 삽입하여 거리 순서를 유지합니다.
- 탐색 종료 후 목적지의 거리 값이 무한대(INF)면 도달 불가능(-1), 아니면 그 값을 출력합니다.
위 접근을 의사 코드로 표현하면 다음과 같습니다.
N := 100
정수 쌍 s, t를 정의한다.
크기 N의 배열 grid를 정의한다.
크기 N x N의 배열 dst를 정의한다.
정수 a, b, e를 담는 구조체 node를 정의한다.
check(a, b) 함수:
return a >= 0 AND a < h AND b >= 0 AND b < w
bfs(a, b) 함수:
i := 0부터 i < h일 때까지 1씩 증가하며 반복:
j := 0부터 j < w일 때까지 1씩 증가하며 반복:
dst[i, j] := 무한대
dst[a, b] := 0
덱 doubleq를 정의한다.
{a, b, dst[a, b]} 노드를 doubleq의 뒤에 삽입한다.
while (doubleq가 비어 있지 않으면):
nd := doubleq의 첫 번째 원소
if nd.e > dst[nd.a, nd.b]이면:
건너뛰고 다음 반복으로 진행
diffx := -2부터 diffx <= 2일 때까지 1씩 증가하며 반복:
diffy := -2부터 diffy <= 2일 때까지 1씩 증가하며 반복:
tm := |diffx| + |diffy|
nx := nd.a + diffx, ny := nd.b + diffy
if check(nx, ny) AND grid[nx, ny] == '.'이면:
w := (tm > 1이면 1, 아니면 0)
if dst[nd.a, nd.b] + w < dst[nx, ny]이면:
dst[nx, ny] := dst[nd.a, nd.b] + w
if w == 0이면:
{nx, ny, dst[nx, ny]} 노드를 doubleq의 앞에 삽입
else:
{nx, ny, dst[nx, ny]} 노드를 doubleq의 뒤에 삽입
s := c, t := d
s의 첫 번째 값과 두 번째 값을 1씩 감소
t의 첫 번째 값과 두 번째 값을 1씩 감소
i := 0부터 i < h일 때까지 1씩 증가하며 반복:
grid[i] := initGrid[i]
bfs(s의 첫 번째 값, s의 두 번째 값)
dst[t의 첫 번째 값, t의 두 번째 값] == 무한대이면 -1 출력, 아니면 그 값 출력
C++ 구현 예제
아래의 실제 구현 코드를 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
#define N 100
int h, w;
pair<int, int> s, t;
string grid[N];
int dst[N][N];
struct node {
int a, b, e;
};
bool check(int a, int b) {
return a >= 0 && a < h && b >= 0 && b < w;
}
void bfs(int a, int b) {
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++)
dst[i][j] = INF;
}
dst[a][b] = 0;
deque<node> doubleq;
doubleq.push_back({a, b, dst[a][b]});
while (!doubleq.empty()) {
node nd = doubleq.front();
doubleq.pop_front();
if (nd.e > dst[nd.a][nd.b])
continue;
for (int diffx = -2; diffx <= 2; diffx++) {
for (int diffy = -2; diffy <= 2; diffy++) {
int tm = abs(diffx) + abs(diffy);
int nx = nd.a + diffx, ny = nd.b + diffy;
if (check(nx, ny) && grid[nx][ny] == '.') {
int w = (tm > 1) ? 1 : 0;
if (dst[nd.a][nd.b] + w < dst[nx][ny]) {
dst[nx][ny] = dst[nd.a][nd.b] + w;
if (w == 0)
doubleq.push_front({nx, ny, dst[nx][ny]});
else
doubleq.push_back({nx, ny, dst[nx][ny]});
}
}
}
}
}
}
void solve(pair<int,int> c, pair<int, int> d, string initGrid[]){
s = c;
t = d;
s.first--, s.second--, t.first--, t.second--;
for(int i = 0; i < h; i++)
grid[i] = initGrid[i];
bfs(s.first, s.second);
cout << (dst[t.first][t.second] == INF ? -1 :
dst[t.first][t.second]) << '\n';
}
int main() {
h = 4, w = 4;
pair<int,int> c = {2, 1}, d = {4, 4};
string initGrid[] = {"#...", ".##.", "...#", "..#."};
solve(c, d, initGrid);
return 0;
}
입력
4, 4, {2, 1}, {4, 4}, {"#...", ".##.", "...#", "..#."}
출력
1
마무리
이처럼 0-1 BFS를 활용하면 걷기와 점프처럼 비용이 다른 이동이 섞여 있는 문제도 효율적으로 해결할 수 있습니다. 격자의 크기가 h × w일 때 각 셀마다 최대 25개의 인접 후보를 검사하므로 전체 시간 복잡도는 O(h × w × 25), 즉 사실상 O(h × w)로 매우 효율적입니다. 또한 목적지에 도달할 수 없는 경우 -1을 반환하도록 처리했기 때문에 다양한 입력 상황에서도 안정적으로 동작합니다.