[파이썬] 백준 17472 : 다리 만들기 2 (골드1)

[파이썬] 백준 17472 : 다리 만들기 2 (골드1)

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

---

풀이

방향성 생각

• 맵이 작고 섬의 수가 적어서 완탐가능
• MST로 풀이 시, 크루스칼로 그리디 하게 고르면 전부 탐색하지 않고 풀이 가능.

 

---

전체코드

from collections import deque

dires = [(1,0),(0,1),(-1,0),(0,-1)]
inside = lambda x,y : 0<=x<W and 0<=y<H

H,W = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(H)]

number = 1
V = [[0]*W for _ in range(H)]

def bfs(sx,sy):
    V[sy][sx] = number
    Q = deque([(sx,sy)])
    while Q:
        x,y = Q.popleft()
        for dx,dy in dires:
            nx,ny = x+dx,y+dy
            if inside(nx,ny) and arr[ny][nx] and not V[ny][nx]:
                Q.append((nx,ny))
                V[ny][nx] = number

table = {}
for y in range(H):
    for x in range(W):
        if arr[y][x] and not V[y][x]:
            bfs(x,y)
            number += 1

for y in range(H):
    for x in range(W):
        arr[y][x] = V[y][x]
        table[(x,y)] = arr[y][x]

G = []
for y in range(H):
    for x in range(W):

        if not arr[y][x]:
            continue

        for dx,dy in dires:

            conn = True
            locs = [(x,y)]

            for i in range(1,11):
                nx,ny = x+dx*i, y+dy*i

                if not inside(nx,ny) or arr[ny][nx] == arr[y][x]:
                    conn = False
                    break

                locs.append((nx,ny))

                if arr[ny][nx]:
                    break

            if not conn or len(locs) <= 1:
                continue

            if len(locs) > 3:
                G.append([len(locs)-2,table[locs[0]],table[locs[-1]]])
G.sort()

P = [i for i in range(number)]

def find(x):
    if x != P[x]:
        P[x] = find(P[x])
    return P[x]

answer = 0
connect = 0
for cost,a,b in G:
    pa,pb = find(a),find(b)
    if pa!=pb:
        P[max(pa,pb)] = min(pa,pb)
        connect += 1
        answer += cost

for i in range(1,number):
    find(i)

print(answer if connect == number-2 else -1)

코멘트

• 다리 건설하는 부분에서 max(W,H)로 전방 탐색방향을 제한했더니 31%에서 틀렸다...
• 어짜피 break point 있으니까 넉넉하게 잡아주기.