[파이썬] 백준 2146 : 다리 만들기 (골드3)

[파이썬] 백준 2146 : 다리 만들기 (골드3)

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

---

풀이

방향성 생각

• 유니온파인드 / BFS
• 백조의 호수랑 비슷한 흐름인듯?
• 관건은 x - - x로 연결되는거랑 x - x로 연결되는걸 처리했다.
• 각 날짜마다 테두리를 채우는데 위 두 가지 케이스를 구분했다

 

전체코드

from collections import deque, defaultdict as dd
import sys

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

N = int(input())
arr = [list(map(int,input().split())) for _ in range(N)]
V = [[False]*N for _ in range(N)]

def get_boundary(sx,sy,cnt):
    boundary = dd(int)
    V[sy][sx] = True

    Q = deque([(sx,sy)])
    while Q:
        x,y = Q.popleft()

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

            if not inside(nx,ny):
                continue

            if arr[ny][nx]:
                if not V[ny][nx]:
                    V[ny][nx] = True
                    Q.append((nx,ny))
            else:
                # 같은 군집에서 중복 방문을 줄이기
                if not V[ny][nx]:  # -> 첫 방문이면 V에 군집 번호
                    boundary[(nx,ny)] += 1
                    V[ny][nx] = cnt
                elif V[ny][nx] != cnt:  # 군집 번호가 다른 경우에만 +1
                    boundary[(nx,ny)] += 1

    return boundary

# 초기 군집
count = 1
start_boundary = dd(int)
for y in range(N):
    for x in range(N):
        if arr[y][x] and not V[y][x]:
            count += 1
            for (xx,yy),val in get_boundary(x,y,count).items():
                start_boundary[(xx,yy)] += val

# 시뮬레이션
day = 0
while True:

    ncount = 1
    double_connect = False
    for (x,y),val in start_boundary.items():
        arr[y][x] = 1

        # 연결이 되어있는 경우
        if val > 1:
            double_connect = True

    # 딕셔너리 업데이트
    start_boundary = dd(int)
    V = [[False]*N for _ in range(N)]
    for y in range(N):
        for x in range(N):
            if arr[y][x] and not V[y][x]:
                ncount += 1
                for (xx,yy),val in get_boundary(x,y,ncount).items():
                    start_boundary[(xx,yy)] += val

    day += 1
    # 이전과 군집 개수가 달라졌으면 연결됐음. double_connect 경우 길이 -1
    if count != ncount:
        print(2*day - double_connect)
        break
    else:
        count = ncount

코멘트

• 유니온 파인드로 푸는게 훨 나은듯 시간도 그렇고
  • BFS로 돌리려면 grid 전부 탐색해야되는데, 유니온파인드는 테두리 접근이라 빠를듯? (군집 based이면 parent 배열 크기도 작을거라)
• 딕셔너리 업데이트에서 key가 같은 경우에 업데이트하는 val로 덮어써졌다.
  • += 되는거로 생각하고 풀어서 좀 삽질함.