[백준 17472번] 다리만들기2(파이썬)

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

17472번: 다리 만들기 2

상당히 까다로운 문제 중 하나입니다.

다리를 넣고

어떻게 최소 경로를 만들어야하는지에 대해서

상당히 머리가 아픈 문제입니다.

 

우선, 구역을 나누는 건

bfs로 해주면 됩니다.

이렇게 구역나눠주는 건 할만합니다.

 

그 다음에는 다리 만들어주기.

다리를 만드는 조건은 '일자형'입니다.

방향을 중간에 바꾸면 안됩니다.

쭉~~한 방향으로 만.

 

다리를 만들어준 다음에는

'가장 짧은 다리'의 합입니다.

섬을 모두 연결했을 때

가장 짧은 다리를 구하는 것입니다.

 

2022.09.08 - [알고리즘 공부] - [백준 1944번] 복제로봇(파이썬)

[백준 1944번] 복제로봇(파이썬)

사실 3번째 이어주는 건

크루스칼 알고리즘을 알면 해결할 수 있습니다.

섬 하나 하나를 node라고 생각해두고

다른 섬으로 가는 다리를 받아주고

크루스칼로 구하면 됩니다.

 

#백준 17472번 다리만들기2
from collections import deque
from heapq import heappop,heappush
N,M=map(int,input().split())
dx=[0,0,1,-1]
dy=[1,-1,0,0]

room=[list(map(int,input().split())) for _ in range(N)]

visited=[[-1]*M for _ in range(N)]
cnt=1
group=[[]]
def find(u):
    if p[u]!=u:
        p[u]=find(p[u])
    return p[u]


def union(a,b):
    r1=find(a)
    r2=find(b)

    p[r2]=r1

def check(x,y):
    if x<0 or x>=N:
        return False
    if y<0 or y>=M:
        return False
    return True
#1.구역 나누기

for x in range(N):
    for y in range(M):

        if room[x][y]==1 and visited[x][y]==-1:

            q=deque()
            q.append([x,y])

            visited[x][y]=cnt
            tmp=[[x,y]]
            while q:
                #pop 해준 걸 x,y라고 표기해버리면, 전체 루프문의 x,y와 겹칠 수 있다. 그러니 그냥 px,py로 두는 편이 좋다.
                px,py=q.popleft()
                for d in range(4):
                    nx=px+dx[d]
                    ny=py+dy[d]

                    if not check(nx,ny):
                        continue

                    if visited[nx][ny]!=-1:
                        continue
                    if room[nx][ny]==0:
                        continue

                    visited[nx][ny]=cnt
                    q.append([nx,ny])
                    tmp.append([nx,ny])
            cnt+=1
            group.append(tmp)

p=[i for i in range(cnt)]


way=[]


for i in range(1,cnt):
    q=deque(group[i])
    while q:
        x,y=q.popleft()
        for d in range(4):
            nx=x+dx[d]
            ny=y+dy[d]
            if not check(nx,ny):
                continue
            #0이 있는 지역이면 건널 수 있다
            if room[nx][ny]==0:
                road=1
                now=i
                flag=False
                #해당방향으로 쭉 이동
                while check(nx+dx[d],ny+dy[d]):

                    if room[nx+dx[d]][ny+dy[d]]==1:
                        go=visited[nx+dx[d]][ny+dy[d]]
                        flag=True
                        break
                    nx+=dx[d]
                    ny+=dy[d]
                    road+=1
                if flag==False:
                    continue
                if road>=2:

                    if go==i or go<=0:
                        continue
                    heappush(way,[road,i,go])
answer=0
edge=0

while True:

    if edge==len(p)-2:
        break
    if not way:
        print(-1)
        exit(0)
    w,a,b=heappop(way)
    if find(a)!=find(b):
        union(a,b)
        answer+=w
        edge+=1

print(answer)

 

이거 풀면서 실수를 크게 했었는데요.

섬 구하는 부분에서

#으로 적은 부분이 고쳐진 부분입니다.

별 생각없이

x,y=q.popleft()했던 부분을 수정했는데요

제 코드상에서는 전체 for문에

x,y가 있습니다.

그런데 저렇게 구해버리면

전체 for문의 x,y와 

bfs부분의 x,y가 겹치는 일이 생깁니다.

반례를 넣다가 틀린 걸 발견했습니다.

반례 거의 다 맞았는데

제출하자마자 틀렸다고 떠서

진짜 너무 화났는데

저렇게 틀린 부분을 찾아내니 기뻤습니다.