bfs - n개의 섬들을 잇는 최소의 다리

2146

섬들 별로 소속을 가지게 해야할 필요가 있다.
섬들에 번호를 매기는 방식으로 가는 경우 bfs1()은 값이 있는지 본다음 트루면 섬의 번호를 ++

---

origin에 방문한걸 0으로 남기고, 섬의 끝부분을 1로 남기면 bfs1()이
섬의 끝부분1에 대해서 다시 돌게되므로 유용하지 않다.

:::bridge[] 라는 배열 (한 칸당[0,0]) 초기화
[0] : 섬의 소속
[1] : 비용으로 입력

bfs1은 돌면서 bridge[0]을 cnt와 동기화해서 섬의 소속을 기록, [1]에는 비용1로 무조건 초기화

섬의 소속을 구분/방문처리 및 최초의 다리 짓기

1.origin[dy][dx]가 1이고 bridge[dy][dx][0]가 0(소속없음)이면 bridge[0]에 cnt(소속 섬 번호)
2.origin[dy][dx]가 1이고 bridge[dy][dx][0]가 있으면 소속이 있으니 continue
3.origin[dy][dx]가 0이면 다리가 될 최초지점이니 bfs1.queue에는 넣지않는다.(bfs2.queue에 넣을것.)
그리고 bridge[1]에는 1로 초기화 (어떤 섬이든 상관이없다.) [0]에는 소속처리
(1번 조건에 의해 방문처리에서 걸리게 해놓기까지 되는셈)

---

하나씩 돌리면 섬의 갯수 n번만큼씩 돌아야해서 n^2만큼 bfs를 돌려야한다.
:::최초의 다리들은 소속 상관없이 하나의 큐에 넣어서 동시에 진행시킨다.

이렇게 처리하면 소속이 다른 다리끼리 만났을때의 비용의 합의 최솟값만 찾으면 됌

bridge[dy][dx][0]와 [y][x][0]가 같은경우 (소속이 같다면) : continue
다르다면,
0으로 다르면 내 소속으로 옮김. (바다를 만난것이니 다리로 만듦)
0이 아닌데 다른거면 다리끼리 만난 것이므로 다리의 비용의 합을 구한뒤 비교(이때 4방향 다 살펴야한다.)
ㄴ> 옆에서 만난거보다 위로 만난게 더 짧거나 등등..의 4방향을 모두 봐야하므로.

---

import sys
from collections import deque


n = int(input())
origin = []
for _ in range(n):
    origin.append(list(map(int, sys.stdin.readline().strip().split())))
br = [[[0,0] for __ in range(n)] for ___ in range(n)]
cnt = 1

bf2q = deque()
def bfs1(y,x,cnt):
    if origin[y][x] == 0 or br[y][x][0]:
        return False
    q = deque()
    q.appendleft((y,x))
    br[y][x][0] = cnt
    ny = [0,0,1,-1]
    nx = [1,-1,0,0]
    while(q):
        b,a = q.pop()
        for ii in range(4):
            dy = ny[ii] + b
            dx = nx[ii] + a
            if dy < 0 or dx < 0 or dy>=n or dx>=n:
                continue
            if origin[dy][dx]:
                if br[dy][dx][0] == 0:
                    br[dy][dx][0] = cnt
                    q.appendleft((dy,dx))
                    continue
            else:
                br[dy][dx][0] = cnt
                br[dy][dx][1] = 1
                bf2q.appendleft((dy,dx))
    return True

for i in range(n):
    for j in range(n):
        if bfs1(i,j,cnt):
            cnt+=1


# n==1이면 어쩌지?
def bfs2():
    mmin = 100000000
    ny = [1,-1,0,0]
    nx = [0,0,1,-1]
    while(bf2q):
        y,x = bf2q.pop()
        for jj in range(4):
            dy = ny[jj] + y
            dx = nx[jj] + x
            if dy < 0 or dx < 0  or dy>=n or dx>=n:
                continue
            if br[dy][dx][0]==br[y][x][0]:
                continue
            if br[dy][dx][0]==0:
                br[dy][dx][0] = br[y][x][0]
                br[dy][dx][1] = br[y][x][1] + 1
                bf2q.appendleft((dy,dx))
                continue
            else:
                if mmin > (br[y][x][1]+br[dy][dx][1]):
                    mmin = (br[y][x][1]+br[dy][dx][1])
                    continue
    return mmin

print(bfs2())