[BOJ]14868. 문명
❌code1
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
import sys
from collections import deque
def find(x):
if parents[x] == x:
return x
p_x = find(parents[x])
parents[x] = p_x
return p_x
def union(x, y):
p_x = find(x)
p_y = find(y)
parents[p_y] = p_x
def bfs():
global civilization_cnt
dr = (-1, 1, 0, 0)
dc = (0, 0, -1, 1)
year = 0
while q:
year += 1 # 햇수 증가
for _ in range(len(q)):
r, c = q.popleft()
for d in range(4):
nr, nc = r + dr[d], c + dc[d]
if nr < 1 or N < nr or nc < 1 or N < nc:
continue
if civil[nr][nc] == 0: # 문명이 아닌 지역
q.append([nr, nc])
civil[nr][nc] = civil[r][c]
# 인접한 지역의 문명 존재 여부 확인
for nd in range(4):
nnr, nnc = nr + dr[nd], nc + dc[nd]
if nnr < 1 or N < nnr or nnc < 1 or N < nnc:
continue
if civil[nnr][nnc] == 0: # 문명이 없다면 무시
continue
# 다른 문명이 존재하는데 이미 융합된 문명이 아닐 경우 결합
if civil[nr][nc] != civil[nnr][nnc] and \
find(civil[nnr][nnc]) != find(civil[nr][nc]):
union(civil[r][c], civil[nnr][nnc])
civilization_cnt -= 1
if civilization_cnt == 1:
if year == 1:
return 0
return year
# 다른 문명을 만났는데 이미 융합된 문명이 아닐 경우 결합
elif civil[nr][nc] != civil[r][c] and \
find(civil[nr][nc]) != find(civil[r][c]):
union(civil[r][c], civil[nr][nc])
civilization_cnt -= 1
if civilization_cnt == 1:
return year
q.append([nr, nc])
N, K = map(int, input().split())
parents = [0] + list(range(1, K + 1)) # 각 문명의 조상 문명 기록
civil = [[0] * (N + 1) for _ in range(N + 1)] # 각 문명의 번호 기록
civilization_cnt = 0 # 총 문명 개수
q = deque()
for _ in range(K):
row, col = map(int, sys.stdin.readline().split())
civilization_cnt += 1
civil[row][col] = civilization_cnt
q.append([row, col])
print(bfs())
시도
- 각 문명은 자연수를 부여받으며 문명의 조상 문명은
parents에 기록된다. 세계를 나타내는 2차원 배열은civil이며 각 칸에는 문명이 존재한다면 해당 문명의 번호가 적혀있다. - 총 문명의 개수
civilization_cnt를 세고 이 값이 1이 된다면 모든 문명이 융합된 것이므로 탐색을 종료한다. - BFS 탐색을 통해 각 문명의 영역을 증가시킨다. 전파 과정에서 고려해야 하는 경우는 다음과 같다.
- 문명이 없는 칸을 마주친 경우 문명을 전파한다. 즉
civil2차원 배열에 같은 숫자를 기록한다.- 문명이 전파된 칸에서 상하좌우를 다시 탐색하여 인접한 칸에 문명이 존재하는지 여부를 확인하고 만약 다른 문명이 존재하는데
find()로 찾은 조상 문명이 같지 않은 경우 즉, 이미 융합된 문명이 아닐 경우union()을 통해 결합한다. - 이때 총 문명의 개수를 감소시키고 만약 이 값이
1이 된다면 탐색을 종료한다.
- 문명이 전파된 칸에서 상하좌우를 다시 탐색하여 인접한 칸에 문명이 존재하는지 여부를 확인하고 만약 다른 문명이 존재하는데
- 문명이 이미 있는 칸을 마주쳤으며
find()로 찾은 조상 문명이 같지 않은 경우 즉, 이미 융합된 문명이 아닐 경우union()을 통해 결합한다.- 이때 총 문명의 개수를 감소시키고 만약 이 값이
1이 된다면 탐색을 종료한다.
- 이때 총 문명의 개수를 감소시키고 만약 이 값이
- 문명이 없는 칸을 마주친 경우 문명을 전파한다. 즉
문제
초기 문명 발상지가 모두 붙어있는 경우 모든 문명이 하나로 결합할 때까지 걸리는 최소 햇수는 0이다. 하지만 위 코드는 이를 판별하지 못한다.
bfs() 함수에서 이를 판별하기 위해선 civilization_cnt를 감소시킬 때 그 이유가 전파된 문명의 인접한 지역이기 때문인지, 초기 발상지끼리 인접해있기 때문인지 구분할 수 있어야 한다. 하지만 전파된 문명의 인접한 지역인 동시에 초기 발상지와 인접해 있는 경우 이는 결국 q에 좌표가 저장된 순서에 따라 정의되기 때문에 bfs()에서 판별할 수 없다.
⭕code2
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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
# 14868. 문명
import sys
from collections import deque
def find(x):
if parents[x] == x:
return x
p_x = find(parents[x])
parents[x] = p_x
return p_x
def union(x, y):
p_x = find(x)
p_y = find(y)
parents[p_y] = p_x
def bfs():
global civilization_cnt
year = 0
while q:
year += 1 # 햇수 증가
for _ in range(len(q)):
r, c = q.popleft()
for d in range(4):
nr, nc = r + dr[d], c + dc[d]
if nr < 1 or N < nr or nc < 1 or N < nc:
continue
if civil[nr][nc] == 0: # 문명이 아닌 지역
q.append((nr, nc))
civil[nr][nc] = civil[r][c]
# 인접한 지역의 문명 존재 여부 확인
for nd in range(4):
nnr, nnc = nr + dr[nd], nc + dc[nd]
if nnr < 1 or N < nnr or nnc < 1 or N < nnc:
continue
if civil[nnr][nnc] == 0: # 문명이 없다면 무시
continue
# 다른 문명이 존재하는데 이미 융합된 문명이 아닐 경우 결합
if civil[nr][nc] != civil[nnr][nnc] and \
find(civil[nnr][nnc]) != find(civil[nr][nc]):
union(civil[r][c], civil[nnr][nnc])
civilization_cnt -= 1
if civilization_cnt == 1:
return year
# 다른 문명을 만났는데 이미 융합된 문명이 아닐 경우 결합
elif civil[nr][nc] != civil[r][c] and \
find(civil[nr][nc]) != find(civil[r][c]):
union(civil[r][c], civil[nr][nc])
civilization_cnt -= 1
if civilization_cnt == 1:
return year
q.append((nr, nc))
def initial_bfs():
global civilization_cnt
# 시작부터 문명끼리 붙어있는지 아닌지 검사
while initial_q:
r, c = initial_q.popleft()
for d in range(4):
nr, nc = r + dr[d], c + dc[d]
if nr < 1 or N < nr or nc < 1 or N < nc:
continue
# 문명이 붙어있는 경우 문명 개수를 줄이고 만약 전부 붙어있다면 False 반환
if civil[nr][nc] and find(civil[nr][nc]) != find(civil[r][c]):
union(civil[r][c], civil[nr][nc])
civilization_cnt -= 1
if civilization_cnt == 1:
return False
return True
N, K = map(int, input().split())
parents = [0] + list(range(1, K + 1)) # 각 문명의 조상 문명 기록
civil = [[0] * (N + 1) for _ in range(N + 1)] # 각 문명의 번호 기록
civilization_cnt = 0 # 총 문명 개수
dr = (-1, 1, 0, 0) # 상하좌우
dc = (0, 0, -1, 1)
q = deque()
initial_q = deque() # initial_bfs()에서 사용할 덱
for _ in range(K):
row, col = map(int, sys.stdin.readline().split())
q.append((row, col))
initial_q.append((row, col))
civilization_cnt += 1
civil[row][col] = civilization_cnt
if initial_bfs():
print(bfs())
else:
print(0)
시도
bfs()에서 초기 발상지가 모두 붙어있는 경우를 판별할 수 없기 때문에 이를 보완해야 한다. bfs() 함수 내부를 수정할 수 있지만, 초기 발상지가 붙어있는지 경우는 초기에 한 번만 검사하면 알 수 있다. 따라서 initial_bfs() 함수를 생성하여 본 탐색 전에 BFS를 통해 초기 발상지끼리 붙어 있는 경우를 검사한다. 만약 이 검사를 통해 모든 문명이 결합된다면 햇수로 0을 출력할 수 있게 된다.
막연히 같은 구조의 코드가 반복되기 때문에 실행 시간이 매우 느릴 줄 알았지만 실제 결과는 빠른 편이었다. 생각해보면 bfs()에서 맨 처음 실행될 작업의 상당수를 initial_bfs()에서 따로 처리하는 것이기 때문에 총 작업에는 큰 변동이 없을 것이다.
요약
- Union-find와 BFS를 이용해 인접한 지역으로의 전파와 지역 간 결합을 탐색할 수 있다.
- 탐색 초기에 추가 검사를 통해 예외상황을 통제할 수 있다.
This post is licensed under CC BY 4.0 by the author.