Boj 9376) 탈옥
문제
방법 1
설명
경우를 최수 두명이 중간에 만나는지 안 만나는지로 나누었다.
- 만나지 않는 경우는 다익스트라로 각각 구해서 더하면 된다.
- 만나는 경우는 위에서 구한
dps[0][],dps[1][]에서 같은 좌표에서의 합이 만나지 않는 경우보다 작은 지점에서 만나서 밖으로 나가야한다. 이때 이 지점은 하나가 아닐 수도 있다. 다익스트라의 초기화 때 이 지점들을 모두 큐에 넣어, 이러한 모든 지점부터의 바깥까지의 최단 거리를 구하자. 이때 정점은pos가 되고 가중치는dps[0][pos] + dps[1][pos]가 된다. 단 넣는 지점이'#'이면 값이 중복되므로 1을 빼주어야 한다.
0-1 너비 우산 탐색
간선이 0~1 뿐이므로 다익스트라에서 priority_queue 를 쓰지 않고 선형 시간에 최단정점을 구하는 0-1 너비 우선 탐색 을 사용할 수 있다. deque 을 사용해 추가되는 weight 가 0 이면 push_front() 를 하고 1이면 push_back() 을 하면 weight 상의 정렬이 유지가 되어 다익스트라의 시간복잡도가 \(\mathrm{O}(\vert V \vert + \vert E \vert)\) 가 된다.
이 기법을 사용하면서 위의 설명대로 여러정점을 넣을 때 정렬을 꼭 적용하자. 우선순위 큐가 아니라서 자동으로 정렬되지 않기 때문이다. 안해도 시간초과가 날 정도로 느려지진 않지먄 40ms -> 16ms 로 꽤 차이가 난다.
시간 복잡도
\(\mathrm{O}(\vert V \vert+ \vert E \vert\))
코드
const int MAX_IN = 101 * 101;
const int INF = 1e9;
char board[MAX_IN];
int dps[2][MAX_IN];
int h, w;
inline bool Valid(int x, int y) { return x >= 0 && y >= 0 && x < w&& y < h; }
inline bool Out(int x, int y) { return x == 0 || y == 0 || x == w - 1 || y == h - 1; }
int xd[] = { -1, 1, 0, 0 };
int yd[] = { 0, 0, -1, 1 };
int Dijkstra(const vector<pair<int, int>>& starts, int* dp)
{
int ans = 1e9;
fill(dp, dp + w * h, INF);
deque<pair<int, int>> q;
for (auto& s : starts)
{
q.push_back({ -s.first, s.second });
dp[s.second] = s.first;
}
while (!q.empty())
{
auto cur = q.front(); q.pop_front();
if (dp[cur.second] < cur.first) continue; // out of updated edge
int x, y;
x = cur.second % w; y = cur.second / w;
if (Out(x, y))
if (ans > dp[cur.second])
ans = dp[cur.second];
for (int i = 0; i < 4; i++)
{
if (!Valid(x + xd[i], y + yd[i])) continue;
int d = (y + yd[i]) * w + x + xd[i];
if (board[d] == '*') continue;
int w = board[d] == '.' ? 0 : 1;
if (dp[cur.second] + w < dp[d])
{
dp[d] = dp[cur.second] + w;
w ? q.push_back({dp[d], d }) : q.push_front({dp[d], d });
}
}
}
return ans;
}
int main()
{
int T;
cin >> T;
while (T--)
{
vector<int> pris; int ans = INF;
cin >> h >> w;
for (int i = 0; i < w * h; i++)
{
cin >> board[i];
if (board[i] == '$') {
pris.push_back(i);
board[i] = '.';
}
}
// 겹치지 않는 경우
ans = Dijkstra({ {0, pris[0]} }, dps[0]) + Dijkstra({ {0, pris[1]} }, dps[1]);
// 겹치는 경우
vector<pair<int, int>> pts;
for (int i = 0; i < w * h; i++)
{
int cost = dps[0][i] + dps[1][i] + (board[i] == '#' ? -1 : 0);
if (dps[0][i] != INF && cost < ans)
pts.push_back({ cost, i });
}
sort(pts.begin(), pts.end()); // 이거 없으면 느려짐
ans = min(ans, Dijkstra(pts, dps[0]));
cout << ans << '\n';
}
}방법 2
설명
모든 지점에서 바깥까지의 거리 + 죄수1까지의 거리 + 죄수2까지의 거리 를 구한다. 선택된 지점 이전에는 최수가 만나지 않았다고 가정한다. 먄약 선택된 지점으로 가는 도중에 죄수가 만난다면 문을 연 횟수가 중복되어 더해지므로 최솟값이 될 수 없어 상관없다.
바깥까지의 거리를 구하기 위해서 바깥에 빈공간을 한겹 만들어서 처리한다. 자세한건 여기 참고.
이 방법이 비교적 더 빠르고, 0-1 너비 우선 탐색을 사용하지 않으면 2배 이상 더 빨랐다. 방법 1과 하는 작업은 크게 다르지 않지만 정점을 구해서 옮기는 과정에서 오버헤드가 있기 때문으로 보인다.
시간 복잡도
\(\mathrm{O}(\vert V \vert+ \vert E \vert\))
코드
const int MAX_IN = 103 * 103;
const int INF = 1e9;
char board[MAX_IN];
int dps[3][MAX_IN];
int h, w;
inline bool Valid(int x, int y) { return x >= 0 && y >= 0 && x < w&& y < h; }
inline bool Out(int x, int y) { return x == 0 || y == 0 || x == w - 1 || y == h - 1; }
int xd[] = { -1, 1, 0, 0 };
int yd[] = { 0, 0, -1, 1 };
void Dijkstra(const vector<pair<int, int>>& starts, int dest, int* dp)
{
fill(dp, dp + w *h, INF);
deque<pair<int, int>> q;
for (auto& s : starts)
{
q.push_back({ -s.first, s.second });
dp[s.second] = s.first;
}
while (!q.empty())
{
auto cur = q.front(); q.pop_front();
if (dp[cur.second] < cur.first) continue; // out of updated edge
int x, y;
x = cur.second % w; y = cur.second / w;
for (int i = 0; i < 4; i++)
{
if (!Valid(x + xd[i], y + yd[i])) continue;
int d = (y + yd[i]) * w + x + xd[i];
if (board[d] == '*') continue;
int w = board[d] == '.' ? 0 : 1;
if (dp[cur.second] + w < dp[d])
{
dp[d] = dp[cur.second] + w;
w ? q.push_back({dp[d], d }) : q.push_front({dp[d], d });
}
}
}
}
int main()
{
fastio;
int T;
cin >> T;
while (T--)
{
vector<int> pris; int ans = INF;
cin >> h >> w;
h += 2; w += 2;
fill(board, board + w * h, '.');
for (int i = 1; i < h-1; i++)
for(int j = 1; j < w-1; j++)
{
int cur = i * w + j;
cin >> board[cur];
if (board[cur] == '$') {
pris.push_back(cur);
board[cur] = '.';
}
}
Dijkstra({ {0, pris[0]} }, -1, dps[0]);
Dijkstra({ {0, pris[1]} }, -1, dps[1]);
Dijkstra({ {0, 0} }, -1, dps[2]);
vector<pair<int, int>> pts;
for (int i = 0; i < w * h; i++)
if (dps[0][i] != INF && dps[1][i] != INF && dps[2][i] != INF)
{
int cost = dps[0][i] + dps[1][i] + dps[2][i] + (board[i] == '#' ? -2 : 0);
ans = min(cost, ans);
}
cout << ans << '\n';
}
}
댓글남기기