[파이썬] 백준 14868 : 문명 (플레4)

[파이썬] 백준 14868 : 문명 (플레4)

• https://www.acmicpc.net/problem/14868

---

풀이

방향성 생각

• BFS + 유니온파인드
  • 백조의호수?랑 비슷해서 방향성은 바로 찾았다.
• 중요한 점은, 각 노드마다 parent를 설정하면 map size가 굉장히 커서 시간 소모가 굉장히 크다는 점.
• 각 문명마다 번호를 매긴다.
  • 시작점에서 붙어있는 경우를 생각하기 위해 BFS 사용하기.
  • parent에서 K만큼 쌩으로 쓰는 것 보다 메모리를 꽤나 절약할 수 있다.
  • visit 배열 첫 방문이면 그 문명으로 넘어가고, 두 번째 방문이면 union을 진행하면 된다.
• 문명이 합쳐지는 경우는 두 가지
  • axb -> aab로 합쳐지는 경우
    • 이 경우는 첫방문인 x->a에서 a로 합쳐지고 b에서 탐색 시 알아서 합쳐진다.
  • axxb -> aabb로 합쳐지는 경우
    • 이 경우는 도착노드 x->a랑, x->b node에서 한 번더 주변 노드를 탐색한다.
  • 문명이 합쳐질 때, 카운팅을 해줘야한다.
    • 첫 BFS를 제외하고 군집의 수를 count 변수에 담아놨다.
    • 각 집합이 모두 연결되려면 총 count-1개의 간선(유니온)이 필요함

 

---

전체코드

from collections import deque
import sys

input = sys.stdin.readline
inside = lambda x,y: 0<=x<N and 0<=y<N
dire = [(1,0),(0,1),(-1,0),(0,-1)]

N,K = map(int,input().split())

# 시작점 starts에를 받고, V에 시작점 표시 -1을 한다.
V = [[0]*N for _ in range(N)]
starts = []
for _ in range(K):
    a,b = map(lambda x: int(x)-1,input().split())
    starts.append((a,b))
    V[b][a] = -1

# 첫 union은 BFS로 진행한다.
def first_union(x,y,idx):
    global V
    Q = deque([(x,y)])
    V[y][x] = idx
    civils.append((x,y,idx))
    while Q:
        x,y = Q.popleft()
        for dx,dy in dire:
            nx,ny = x+dx,y+dy
            if inside(nx,ny) and V[ny][nx] == -1:
                Q.append((nx,ny))
                V[ny][nx] = idx
                civils.append((nx,ny,idx))

civils = deque()
count = 0
for x,y in starts:
    if V[y][x] == -1:
        count += 1
        first_union(x,y,count)

P = [i for i in range(count+1)]
def find(x):
    if P[x] != x:
        P[x] = find(P[x])
    return P[x]

def union(x,y):
    global connection
    px,py = find(x),find(y)
    if px != py: # 첫 방문이 아닌 경우에만 (두 문명이 만날 때) 진행하므로 연결 수를 카운팅
        P[max(px,py)] = P[min(px,py)]
        connection += 1

# 시작점과 그 문명 번호를 담은 civils에서 탐색 진행
def bfs(Q):
    nQ = deque()
    while Q:
        x,y,idx = Q.popleft()

        for dx,dy in dire:
            nx,ny = x+dx,y+dy

            if inside(nx,ny) and not V[ny][nx]: # 첫 방문인 경우만 탐색
                nQ.append((nx,ny,idx))
                V[ny][nx] = idx

                for dx,dy in dire: # 도착지점에서 유니온을 해야할지 탐색
                    nnx,nny = nx+dx,ny+dy
                    if inside(nnx,nny) and V[nny][nnx]:
                        union(idx,V[nny][nnx])
    return nQ

answer,connection = 0,0
while connection < count-1:
    answer += 1
    civils = bfs(civils)
print(answer)

코멘트

• union에서 부모노드 말고 자식노드로 합쳐서 한참 찾았다...