백준 2146 다리 만들기

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

2146번: 다리 만들기

어제 이걸못풀어서  접을까 생각했다.

 

1. 일단, 모든 섬을 구분한다. (bfs1)

 

2. 섬의 가장자리(edge)좌표를 모두 구한다.

 

3. edge를 바탕으로 (bfs2) 를 진행하며, 바다를 그 섬으로 메워나간다

bridge배열을 만들어서, 메운 위치에 1씩 +하며 메운 점 갯수를 센다.

메워나가다가, 만일 자기 섬도 아니고 바다도 아닌 다른 섬을 만나면 이제 다리가 이어진것이다.

그러면 bridge의 현위치+만난위치가 경로이다.

 

여기서 한참을 헤멨는데,

당연히 먼져 도달한 것이 최소경로라고 생각했다. 하지만......

5

1 0 0 0 1

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

0 1 0 0 1

다음과같은 반례가 있다. 최소경로는 4,2   4,3 을 이은 2이지만,

문제는 먼져  왼쪽위와 오른쪽위가 디큐에 들어가므로, 맨 아랫쪽보다 먼져 만나게 된다.

그래서 answer과 만났을때의 합을 계속 비교하며, 최솟값을 찾는 식으로 풀었다.

다시풀으라고하면 또 잊어버려서 헤멜거같다.

 

 

import sys
input=sys.stdin.readline
from collections import deque
moves=[(-1,0),(1,0),(0,-1),(0,1)]
def bfs1(i,j,num): #섬클러스터링
    
    que=deque()
    arr[i][j]=num
    que.append((i,j))
    while que:
        i,j=que.popleft()
        
        for a,b in moves:
            tmp_i,tmp_j=i+a,j+b
            if 0<=tmp_i<n and 0<=tmp_j<n :
                if arr[tmp_i][tmp_j]==1:
                    arr[tmp_i][tmp_j]=num
                    que.append((tmp_i,tmp_j))

                elif arr[tmp_i][tmp_j]==0:
                    edge.append((i,j,num,0))
    return

def dfs2(): #다리놓기
    global answer
    queque=deque(edge)

    while queque:
        i,j,num,cnt=queque.popleft()
        for a,b in moves:
            tmp_i,tmp_j=i+a,j+b
            if 0<=tmp_i<n and 0<=tmp_j<n:
                if arr[tmp_i][tmp_j]==0:
                    arr[tmp_i][tmp_j]=num
                    brigde[tmp_i][tmp_j]=cnt+1
                    queque.append((tmp_i,tmp_j,num,cnt+1))
                
                elif arr[tmp_i][tmp_j]!=num:
                    answer=min(answer,cnt+brigde[tmp_i][tmp_j]) 
                    
                    

    

    




answer=1e+10
n=int(input())
arr=[ [* map (int,input().split())]for _ in range(n)]
brigde=[[False for _ in range(n)]for _ in range(n)]
num=2
edge=[]
for i in range(n):
    for j in range(n):
        if arr[i][j]==1:
            bfs1(i,j,num)
            num+=1
        else:
            continue
edge=list(set(edge))
dfs2()
print(answer)