[BOJ]14868. 文明.
38591 ワード
文明
各文明は自然数を与えられ、文明の祖先文明は 総文明個数 BFS探索を通じて、各文明分野を増やした.伝播の過程で考慮すべき状況は以下の通りである. 文明のない格子に出会って、文明を伝播します.すなわち、 文明を伝播する格子の中で、上下左右を再探索し、隣接する格子の中に文明が存在するかどうかを確認し、他の文明が存在する場合、 では総文明個数を減らし,この値が 文明はすでに存在する格子に遭遇し、 では総文明個数を減らし,この値が
初期の文明発祥地が貼られていれば、すべての文明が結合するまでに必要な最小年数は0である.しかし、上記のコードでは判断できません.
同じ構造のコードを繰り返すため,実行時間は遅いと思われるが,実際の結果はまだ速い.考えてみれば、
Union‐FindとBFSを用いて,近隣地域への伝播と地域間の結合を探索できた. 探索初期には,追加検査により例外を制御できる.
❌code1
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に記録されている.世界を表す二次元配列はcivilで、それぞれに文明的な番号が書かれています.civilization_cntを数え、この値が1であればすべての文明が融合し、探索を終了する.civilの2次元配列に同じ数字が記録される.find()で探した祖先文明は異なり、すなわち融合した文明ではない場合、union()を通じて結合する.1であれば探索を終了する.find()で探していた祖先文明が異なる場合、すなわち融合した文明ではなく、union()を通じて結合している.1であれば探索を終了する.質問する
初期の文明発祥地が貼られていれば、すべての文明が結合するまでに必要な最小年数は0である.しかし、上記のコードでは判断できません.
bfs()関数からこの点を判別するために、civilization_cntを減らす際には、文明を伝播する近隣地域であるためなのか、初期発祥地に隣接しているためなのかを区別できるはずです.しかし、文明が伝播する近隣地域であり、かつ初期発祥地に隣接している場合、これは最終的にqに座標が格納されている順序で定義されるため、bfs()では判別できない.⭕code2
# 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()で単独で処理されるため、総タスクに大きな変動はありません.サマリ
Reference
この問題について([BOJ]14868. 文明.), 我々は、より多くの情報をここで見つけました https://velog.io/@alexuh/boj14868テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol