백준5813 city

작성일 | In

문제 링크

  • http://icpc.me/5813

문제 출처

  • 2012 IOI Day2 1번

사용 알고리즘

  • DFS

풀이

백준 5813


4번째로 쓰는 ioi문제 풀이입니다.

문제에 주어진 조건을 보면 블록이 있는 칸끼리 서로 연결되어 있고, 그렇지 않은 칸끼리도 서로 연결되어 있습니다.
이 말은 블록이 있는 칸 사이에는 경로가 항상 존재하고, 블록이 없는 칸 사이에도 항상 경로가 존재합니다.

문제를 아래와 같이 총 4단계로 나누어 풀어보겠습니다.

  1. 문제가 1차원이라면?
  2. 트리의 모든 정점 사이의 거리의 합
  3. subtask3
  4. 전체 문제
문제가 1차원이라면?

문제를 2차원이 아닌 1차원이라고 생각해봅시다.
블록이 있는 칸은 모두 연결이 되어있으므로 선분 하나만 존재할 것입니다. 이런 경우에는 (i < j)인 모든 |xi - xj|의 합을 O(n log n)만에 정렬 후 O(n)에 구할 수 있습니다.

트리의 모든 정점 사이의 거리의 합

이번에는 트리에서 모든 정점 사이의 거리의 합을 구하는 방법을 생각해봅시다. 아래 코드를 통해 쉽게 구할 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11
void dfs(int now, int prv, ll &dist){
	for(auto nxt : g[now]){
		if(nxt ^ prv && !chk[nxt]){
			chk[nxt] = 1;
			dfs(nxt, now, dist);
			size[now] += size[nxt];
		}
	}
	ll tmp = (ll)size[now] * (ll)(n - size[now]);
	dist += tmp;
}
subtask3

섭테3은 아래 조건을 만족합니다.

  • X[i] = X[j]인 임의의 두 비어있지 않은 셀들이 주어질 때, 그들 사이의 모든 셀들 또한 비어있지 않다.
  • Y[i] = Y[j]인 임의의 두 비어있지 않은 셀들이 주어질 때, 그들 사이의 모든 셀들 또한 비어있지 않다.

이 조건을 만족하면 각 셀 사이의 이동 거리는 무조건 |xi - xj| + |yi - yj|입니다.
블록들을 행 별로 분리해서 x 좌표의 거리를 구하고, 열 별로 분리해서 y 좌표의 거리를 구하면 답을 구할 수 있습니다.

전체 문제

블록이 있는 셀들을 행 단위로 잘라내어봅시다.


붙어있는 셀들(덩어리)을 하나의 정점으로 만들고, 인접한 덩어리끼리 간선으로 이어주면 아래 그림과 같이 그래프가 만들어집니다.


만들어지는 그래프는 문제의 조건에 의해 사이클이 없고, 모든 정점이 연결되어 있으므로 트리가 됩니다.
위 사진에 있는 트리에서 정점들 사이의 거리는 y축으로 평행하게 이동하는 거리와 동일합니다. 그러므로 트리의 정점들 사이의 거리의 합을 구하면 y 변화량을 구할 수 있습니다.

x좌표와 y좌표를 바꾸어서 적절히 처리를 해준다면 x변화량도 구할 수 있습니다.

전체 코드

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
81
82
83
84
85
86
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef long long ll;
typedef pair<int, int> p;

const int mod = 1e9;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};

int size[101010];
int  chk[101010];
int n;
map<p, int> mp;
set<int> g[101010];

void dfs(int now, int prv, ll &dist){
	for(auto nxt : g[now]){
		if(nxt ^ prv && !chk[nxt]){
			chk[nxt] = 1;
			dfs(nxt, now, dist);
			size[now] += size[nxt];
		}
	}
	ll tmp = (ll)size[now] * (ll)(n - size[now]);
	tmp %= mod;
	dist += tmp; dist %= mod;
}

ll getDist(){
	ll ret = 0;
	chk[1] = 1;
	dfs(1, 0, ret);
	return ret;
}

void makeTree(vector<p> &v){
	sort(v.begin()+1, v.end());
	memset(size, 0, sizeof size);
	memset(chk, 0, sizeof chk);
	for(int i=0; i<=n; i++) g[i].clear();
	mp.clear();

	int cnt = 1;
	mp[v[1]] = cnt;
	size[cnt]++;
	for(int i=2; i<=n; i++){
		if(v[i-1].x == v[i].x && v[i-1].y+1 == v[i].y){
			mp[v[i]] = cnt;
		}
		else mp[v[i]] = ++cnt;
		size[cnt]++;
	}

	for(int i=1; i<=n; i++){
		int x = v[i].x, y = v[i].y;
		int now = mp[v[i]];
		for(int k=0; k<4; k++){
			int xx = x + dx[k];
			int yy = y + dy[k];
			int nxt = mp[{xx, yy}];
			if(nxt && now != nxt) g[now].insert(nxt);
		}
	}
}

int DistanceSum(int N, int *X, int *Y){
	n = N;
	ll ret = 0;
	vector<p> v(n+1);
	for(int i=0; i<n; i++){
		v[i+1] = {X[i], Y[i]};
	}
	makeTree(v);
	ret += getDist() % mod;

	for(int i=0; i<n; i++){
		v[i+1] = {Y[i], X[i]};
	}
	makeTree(v);
	ret += getDist() % mod;
	ret %= mod;
	return (int)ret;
}