[백준 2146] 다리 만들기

문제 

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

 

알고리즘

1. bfs그래프 탐색을 통해서 1로 되어 있는 땅을 2, 3, 4 .. 으로 각 구역을 숫자로 구분한다

2. 다음 bfs 탐색을 통해서 시작 구역의 위치를 queue에 담아둔다 

3. 탐색 과정에서 자신의 구역과 다른 구역을 만났을 때 최단거리를 반환한다 

코드 

import sys
from collections import deque

def Input_Data():
    input = sys.stdin.readline
    N = int(input())
    graph = []
    for _ in range(N+1):
        graph.append(list(map(int, input().split())))
    return N, graph

d = ((0,1),(0,-1),(1,0),(-1,0))
def Bfs(area, i, j):
    q = deque()
    q.append((i,j))
    graph[i][j] = area
    visited[i][j] = 1
    while q:
        x, y = q.popleft()
        for dx, dy in d:
            nx, ny = x + dx, y + dy
            if not (0<=nx<N and 0<=ny<N): continue
            if visited[nx][ny] == 0 and graph[nx][ny] > 0: 
                graph[nx][ny] = area
                visited[nx][ny] = 1
                q.append((nx,ny))

def Bridge_Bfs(v):
    q = deque()
    for i in range(N):
        for j in range(N):
            if graph[i][j] == v:
                q.append((i,j))
                visited[i][j] = 0
    while q:
        x, y = q.popleft()
        for dx, dy in d:
            nx, ny = x + dx, y + dy
            if not (0<=nx<N and 0<=ny<N): continue
            # 다른 섬을 만난 경우 
            if graph[nx][ny] != v and graph[nx][ny] > 0 :
                return visited[x][y]
            # 물을 지나가는 경우 
            if visited[nx][ny] == -1 and graph[nx][ny] == 0:
                visited[nx][ny] = visited[x][y] + 1
                q.append((nx,ny))  
    return 1e9                 

N, graph = Input_Data()
visited = [[0] * (N) for _ in range(N)]
cnt = 1
for i in range(N):
    for j in range(N):
        if graph[i][j] == 1 and visited[i][j] == 0:
            cnt+=1 
            Bfs(cnt, i, j)

ans = 1e9
for i in range(2, cnt+1):
    visited = [[-1] * (N) for _ in range(N)]
    ans = min(ans, Bridge_Bfs(i))
print(ans)