[BOJ/백준] 2146 다리 만들기

import sys
from collections import deque
def input():
    return sys.stdin.readline().rstrip()

def island_bfs(x,y):
    queue = deque()
    queue.append((x,y))
    visited[x][y] = True
    island_check[x][y] = island_cnt
    temp = [(x,y)]
    while queue:
        x,y = queue.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<N and 0<=ny<N:
                if not visited[nx][ny] and arr[nx][ny]:
                    visited[nx][ny] = True
                    island_check[nx][ny] = island_cnt
                    queue.append((nx,ny))
                    temp.append((nx,ny))
    island_list.append(temp)



N = int(input())

arr = [list(map(int,input().split())) for _ in range(N)]
visited = [[False for _ in range(N)] for _ in range(N)]
island_list = []
island_check = [[0 for _ in range(N)] for _ in range(N)]
island_cnt = 1
dx = [-1,0,1,0]
dy = [0,-1,0,1]
for x in range(N):
    for y in range(N):
        if arr[x][y] and not visited[x][y]:
            island_bfs(x,y)
            island_cnt += 1

result = float('inf')


for island_num in range(len(island_list)):
    queue = deque(island_list[island_num])

    visited = [[0 for _ in range(N)] for _ in range(N)]
    dis = 1
    while queue:
        q_size = len(queue)
        flag = False
        for _ in range(q_size):
            x,y = queue.popleft()

            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0<=nx<N and 0<=ny<N:
                    if island_check[nx][ny] != island_num+1 and not visited[nx][ny]:
                        visited[nx][ny] = dis
                        queue.append((nx,ny))
                        if island_check[nx][ny]:
                            result = min(result,dis-1)
                            flag = True
                            break
            if flag:
                break
        if flag:
            break
        dis += 1

print(result)

가장 첫 풀이는 직관적으로 푼 방식으로 각 섬들을 번호를 마킹해주고, 

 

한 섬의 있는 위치에서 다른 섬에 도착하는 최단 거리를 구해주는 방식이다.

 

 

import sys
from collections import deque
def input():
    return sys.stdin.readline().rstrip()

def island_bfs(x,y):
    queue = deque()
    queue.append((x,y))
    visited[x][y] = True
    island_check[x][y] = island_cnt
    temp = [(x,y)]
    while queue:
        x,y = queue.popleft()
        bridge_queue.append((x,y,island_cnt,0))
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<N and 0<=ny<N:
                if not visited[nx][ny] and arr[nx][ny]:
                    visited[nx][ny] = True
                    island_check[nx][ny] = island_cnt
                    queue.append((nx,ny))
                    temp.append((nx,ny))
    island_list.append(temp)

def bfs():
    global result
    while bridge_queue:
        x,y,island_num,dis = bridge_queue.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<N and 0<=ny<N:
                if island_check[nx][ny] == island_num:
                    continue
                if result <= distance_list[nx][ny]:
                    return
                if not distance_list[nx][ny]:
                    distance_list[nx][ny] = dis + 1
                    island_check[nx][ny] = island_num
                    bridge_queue.append((nx,ny,island_num,dis+1))
                else:
                    if result > distance_list[nx][ny] + distance_list[x][y]:
                        result = distance_list[nx][ny] + distance_list[x][y]

N = int(input())

arr = [list(map(int,input().split())) for _ in range(N)]
visited = [[False for _ in range(N)] for _ in range(N)]
island_list = []
island_check = [[0 for _ in range(N)] for _ in range(N)]
island_cnt = 1
dx = [-1,0,1,0]
dy = [0,-1,0,1]
bridge_queue = deque()
for x in range(N):
    for y in range(N):
        if arr[x][y] and not visited[x][y]:
            island_bfs(x,y)
            island_cnt += 1

result = float('inf')

distance_list = [[0 for _ in range(N)] for _ in range(N)]

bfs()

                
print(result)

이 방식은 좀 더 빨리 풀 수 잇는 방식으로 위에서는 1섬마다 전부 초기화를 하고, 매번 구하는것에 반해

 

이 방식은 모든 섬에서 bfs를 동시에 시작하는 것이다.

 

만약 초기 상태의 점을 방문하게 되면, 해당 위치까지의 거리를 distance_list에 넣어주고, island_check에 해당 위치가 어느 섬에서 왔는지 마킹을 해준다.

 

그리고 만약 초기화 된 값이 아닌 이미 있는 값이라면, 비교를 해서 현재 위치의 distance_list[x][y] 와 distance_list[nx][ny]를 더한 값이 더 작으면 갱신을 해준다.

 

그리고 result가 distance_list[nx][ny]보다 작을 시에는 더 갱신할 경우의 수가 없으므로 함수를 종료해준다.