문제
16930번: 달리기
진영이는 다이어트를 위해 N×M 크기의 체육관을 달리려고 한다. 체육관은 1×1 크기의 칸으로 나누어져 있고, 칸은 빈 칸 또는 벽이다. x행 y열에 있는 칸은 (x, y)로 나타낸다. 매 초마다 진영이는
www.acmicpc.net
진영이는 다이어트를 위해 N×M 크기의 체육관을 달리려고 한다. 체육관은 1 ×1 크기의 칸으로 나누어져 있고, 칸은 빈칸 또는 벽이다. x행 y열에 있는 칸은 \((x, y)\)로 나타낸다.
매 초마다 진영이는 위, 아래, 오른쪽, 왼쪽 중에서 이동할 방향을 하나 고르고, 그 방향으로 최소 1개, 최대 K개의 빈칸을 이동한다.
시작점 \((x_1, y_1)\)과 도착점 \((x_2, y_2)\)가 주어졌을 때, 시작점에서 도착점으로 이동하는 최소 시간을 구해보자.
발상
쉽게 생각할 수 있는 풀이는 아래와 같이 현재 정점에서 상하좌우 K 개씩 총 4K 개의 정점을 확인해 경로를 갱신하는 방법으로 도착점까지 최단 거리를 구하는 방법이다. 코드로 나타내면 아래와 같다.
while (!q.empty()) {
auto [x, y] = q.front();
q.pop();
for (int dir = 0; dir < 4; dir++) {
int nx = x;
int ny = y;
for (int i = 1; i <= k; i++) {
nx += dx[dir];
ny += dy[dir];
if (!inside(nx, ny)) break;
if (board[ny][nx] == '#') break;
if (dist[ny][nx] == -1) {
dist[ny][nx] = dist[y][x] + 1;
q.emplace(nx, ny);
}
}
}
}이차원 배열에서 네 방향으로 BFS를 수행했을 때 시간복잡도가 \(O(NM)\)인 것을 감안하면 위 코드의 시간복잡도는 \(O(NMK)\)이 된다. 이 경우 입력의 제한이 2 \(\le\) N, M \(\le\) 1000, 1 \(\le\) K \(\le\) 1000이므로 위 코드는 시간초과이다.
시간초과 이유
위 코드는 현재 정점에서 K만큼 떨어진 모든 정점과 방문 체크 및 거리 갱신을 하고 있기 때문에 현재 정점에서 각 방향으로 K-1번 중복된 비교를 하고 있다. 예를 들어 N = 6, M = 7, K = 3이고 출발점이 (1, 1) 일 때 출발점에서 한번 인접한 정점들의 거리를 갱신하면 아래와 같다.
(1, 2)는 아래 방향으로 (1, 3), (1, 4), (1, 5)와 비교하고 있고 (1, 3)은 아래 방향으로 (1, 4), (1, 5), (1, 6)과 비교하고 있다. (1, 2)와 (1, 3)은 모두 (1, 4)와 (1, 5)를 중복해서 탐색하고 있다. 따라서 현재 정점에서 방향마다 K-1번의 중복 비교가 발생한다.
풀이
(1, 2)에서 방문 체크와 거리를 갱신해야 하는 (1, 5)와 (1, 3)에서 방문 체크와 거리를 갱신해야 하는 (1, 6)은 (1, 4)에서 갱신해야 하는 정점에 포함된다. 또한 (2, 1)과 (2, 2)에서 오른쪽 방향으로 탐색할 정점은 (2, 4)에서 오른쪽 방향으로 탐색할 정점에 포함된다. 이 특징을 활용해 현재 정점에서 꼭 방문해야 하는 정점만 방문해 시간복잡도를 줄일 수 있다.
위의 예시처럼 출발점 (1, 1)에서 각 방향으로 3개의 정점을 탐색한 후 다음 탐색에서는 (1, 4)와 (4, 1)에서 탐색을 이어나가면 중복 탐색이 발생하지 않는다. 즉 출발점에서 각 방향으로 K개의 정점을 탐색하여 나온 영역의 테두리에서 다시 탐색을 이어가면 된다. 이렇게 되면 모든 정점은 한 번씩만 방문하고 간선의 개수도 줄어들어 시간복잡도가 O(NM)이 된다.
이전 영역의 테두리를 찾기 위해서는 테두리가 아닌 정점을 방문하지 않으면 되는데 BFS의 특성으로 인해 현재 정점에서 다음 정점을 탐색할 때 이미 최단 거리가 갱신되어 있으며 그 값이 같은 경우 반복문을 종료하면 된다.
#include <bits/stdc++.h>
using namespace std;
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, m, k;
cin >> n >> m >> k;
char board[1004][1004];
for (int y = 0; y < n; y++) cin >> board[y];
int x1, y1, x2, y2;
cin >> y1 >> x1 >> y2 >> x2;
x1--; y1--; x2--; y2--;
auto inside = [&](int x, int y) -> bool {
return 0 <= x && x < m && 0 <= y && y < n;
};
queue<pair<int, int>> q;
q.emplace(x1, y1);
int dist[1004][1004];
memset(dist, -1, sizeof(dist));
dist[y1][x1] = 0;
while (!q.empty()) {
auto [x, y] = q.front();
q.pop();
for (int dir = 0; dir < 4; dir++) {
int nx = x;
int ny = y;
for (int i = 1; i <= k; i++) {
nx += dx[dir];
ny += dy[dir];
if (!inside(nx, ny)) break;
if (board[ny][nx] == '#') break;
if (dist[ny][nx] != -1 && dist[ny][nx] == dist[y][x]) break;
if (dist[ny][nx] != -1) continue;
dist[ny][nx] = dist[y][x] + 1;
q.emplace(nx, ny);
}
}
}
cout << dist[y2][x2];
return 0;
}
댓글