BOJ 10120 The Wall
sorohue가 PS하는 블로그
문제 링크입니다.
문제 요약
$N \times M$ 크기의 격자가 주어집니다. 격자를 이루는 각 선분은 비용을 갖습니다. 이 격자의 칸 중 일부(마을이라 칭합니다)를 최소 비용으로 모두 둘러싸는 회로를 찾으세요. 같은 선분을 여러 번 지날 수 있습니다.
가장 왼쪽 위 칸은 항상 마을입니다.
풀이
편의상 $(1,1)$을 가장 왼쪽 위 격자점의 좌표로, $(N+1, M+1)$ 가장 오른쪽 아래 격자점의 좌표로 사용합니다.
마을이 서로 연결되어 있는 상황을 생각해 봅시다. 이때의 최적의 회로는 $(1, 2)$에서 $(2, 1)$로 가는 마을 덩어리를 가로지르지 않는 최단 경로를 찾는 식으로 구할 수 있습니다($(1, 1)$로 가는 선분은 쓰지 않아야겠죠).
이 방식에서 우리가 반드시 내부에 포함되어야 하는 지점을 모두 알 수 있다면, 그리고 그것이 하나의 연결 요소를 이룬다면, 다익스트라로 문제를 해결할 수 있다는 점을 알 수 있습니다.
마을이 맨 왼쪽 위 칸을 포함해 둘밖에 없는 상황을 생각합니다. 여기서 $(1,1)$과 다른 마을의 왼쪽 위 꼭짓점을 잇는 최단 경로를 만들면, 놀랍게도 이 최단 경로 위의 모든 점은 회로 내부에 위치해야 합니다. 시작점과 끝점은 무조건 내부에 있어야 되니, 최단 경로 위의 어떤 점이 회로 바깥에 있게 된다는 건 최단 경로랑 회로가 어디서 교차한다는 의미가 됩니다. 이때 교차하는 부분의 회로를 최단 경로의 일부분으로 치환하는 게 이득이고, 따라서 최단 경로 위의 점을 모두 포함하지 않는 회로가 최적일 수 없습니다.
$(1, 1)$에서 각 마을의 왼쪽 위 꼭짓점을 잇는 모든 최단 경로를 얻어 해당 지점들을 내부에 추가하면 아까 마을이 연결되어 있던 상황과 얼추 똑같아집니다. 남은 문제는 어떤 점이나 선분이 회로의 경계에 걸친 경우에 내부인지 외부인지 판정할 수 없다는 점뿐입니다.
이를 해결하기 위해 각 격자점을 넷으로 분할합니다. 각 점이 해당 격자점을 꼭짓점으로 포함하는 네 칸의 귀퉁이에 자리해 있다고 생각하고, 최단 경로를 이루는 선분과 각 마을의 테두리에 해당하는 선분들을 벽으로 취급해 이 점들 사이의 간선을 끊어주면 됩니다. 그러면 각 점이나 선분에서도 내부와 외부를 구분할 수 있으며, 다익스트라를 한 번 더 수행해 문제를 해결할 수 있습니다.
시간 복잡도는 ${\cal O}(NM \lg NM)$입니다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int dy[] = {-1,1,0,0}, dx[] = {0,0,-1,1};
enum Dir{U,D,L,R,};
ll e[821][821][4]; //UDLR
ll dist[821][821];
bool v[444][444];
bool vis[444][444];
void addEdge(int i, int j, int dir, ll w){
e[i][j][dir] = e[i+dy[dir]][j+dx[dir]][dir^1] = w;
}
void dijk(int sy, int sx){
memset(dist, 31, sizeof(dist));
priority_queue<tuple<int,int,int>> pq; dist[sy][sx] = 0;
pq.emplace(0, sy, sx); while(pq.size()){
auto [w, i, j] = pq.top(); pq.pop();
if(-w > dist[i][j]) continue;
for(int dir = 0; dir < 4; dir++) if(e[i][j][dir] >= 0){
int ni = i+dy[dir], nj = j+dx[dir];
if(dist[ni][nj] > -w+e[i][j][dir]){
dist[ni][nj] = -w+e[i][j][dir];
pq.emplace(-dist[ni][nj], ni, nj);
}
}
}
}
int main(){
cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
int n, m; cin >> n >> m;
for(int i = 1; i <= 2*(n+1); i++){
addEdge(i, 1, L, -1);
addEdge(i, 2*(m+1), R, -1);
}
for(int j = 1; j <= 2*(m+1); j++){
addEdge(1, j, U, -1);
addEdge(2*(n+1), j, D, -1);
}
for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) cin >> v[i][j];
for(int i = 1; i <= n; i++) for(int j = 1; j <= m+1; j++){
int w; cin >> w; addEdge(2*i, 2*j-1, D, w); addEdge(2*i, 2*j, D, w);
}
for(int i = 1; i <= n+1; i++) for(int j = 1; j <= m; j++){
int w; cin >> w; addEdge(2*i-1, 2*j, R, w); addEdge(2*i, 2*j, R, w);
}
dijk(1, 1); vis[1][1] = 1;
for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) if(v[i][j]){
addEdge(2*i-1, 2*j, D, -1);
addEdge(2*i-1, 2*j+1, D, -1);
addEdge(2*i, 2*j-1, R, -1);
addEdge(2*i+1, 2*j-1, R, -1);
addEdge(2*i+1, 2*j, D, -1);
addEdge(2*i+1, 2*j+1, D, -1);
addEdge(2*i, 2*j+1, R, -1);
addEdge(2*i+1, 2*j+1, R, -1);
int y = i, x = j;
while(!vis[y][x]){
vis[y][x] = 1;
for(int dir = 0; dir < 4; dir++){
int ny = y+dy[dir], nx = x+dx[dir];
if(dist[2*y-1][2*x-1] == dist[2*ny-1][2*nx-1]+e[2*y-(dir==U)][2*x-(dir==L)][dir]){
addEdge(2*y-(dir==U||dir==R), 2*x-(dir==D||dir==L), dir^2, -1);
addEdge(2*ny-(dir==D||dir==R), 2*nx-(dir==D||dir==R), dir^2, -1);
y = ny; x = nx;
break;
};
}
}
}
addEdge(1, 1, R, -1); addEdge(1, 1, D, -1);
dijk(1, 2); cout << dist[2][1];
}