[BOJ] 2146 다리 만들기 파이썬

www.acmicpc.net/problem/2146

2146번: 다리 만들기

1. 문제

 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다는 생각을 하게 되었다. 그래서 그는, 생색내는 식으로 한 섬과 다른 섬을 잇는 다리 하나만을 만들기로 하였고, 그 또한 다리를 가장 짧게 하여 돈을 아끼려 하였다.

이 나라는 N×N크기의 이차원 평면상에 존재한다. 이 나라는 여러 섬으로 이루어져 있으며, 섬이란 동서남북으로 육지가 붙어있는 덩어리를 말한다. 다음은 세 개의 섬으로 이루어진 나라의 지도이다.

위의 그림에서 색이 있는 부분이 육지이고, 색이 없는 부분이 바다이다. 이 바다에 가장 짧은 다리를 놓아 두 대륙을 연결하고자 한다. 가장 짧은 다리란, 다리가 격자에서 차지하는 칸의 수가 가장 작은 다리를 말한다. 다음 그림에서 두 대륙을 연결하는 다리를 볼 수 있다.

물론 위의 방법 외에도 다리를 놓는 방법이 여러 가지 있으나, 위의 경우가 놓는 다리의 길이가 3으로 가장 짧다(물론 길이가 3인 다른 다리를 놓을 수 있는 방법도 몇 가지 있다).

지도가 주어질 때, 가장 짧은 다리 하나를 놓아 두 대륙을 연결하는 방법을 찾으시오.

2. 입력

첫 줄에는 지도의 크기 N(100이하의 자연수)가 주어진다. 그 다음 N줄에는 N개의 숫자가 빈칸을 사이에 두고 주어지며, 0은 바다, 1은 육지를 나타낸다. 항상 두 개 이상의 섬이 있는 데이터만 입력으로 주어진다.

3. 출력

첫째 줄에 가장 짧은 다리의 길이를 출력한다.

 

4. 해설

 

DFS와 BFS를 모두 사용하여 구현해야한다.

1. DFS를 이용해 전체 섬의 개수를 파악한다.

2. BFS를 이용해 섬 사이 거리를 찾는다.

def dfs(l,visited): # l: 지도, visited: 방문 여부를 체크함
    """ 섬의 개수를 찾는 DFS 함수 """
    def rdfs(i,j,n_isl):
    	""" 재귀적으로 사용할 DFS 함수 """
        # 방문하지 않았고 해당 좌표가 육지(1)이라면
        if visited[i][j] ==False and l[i][j]==1: 
            #방문한 걸로 체크하고 섬의 번호를 적어준다.
            visited[i][j] = True 
            l[i][j] =n_isl
 			# 상하 좌우로 이동해 좌표가 지도 범위안에 있으면
            for k in range(4):
                nx = i + dx[k]
                ny = j + dy[k]
                # 다음 경로에 대해 위 과정을 재귀적으로 시행
                if 0<=nx<N and 0<=ny<N and l[nx][ny] ==1:
                    rdfs(nx,ny,n_isl)
    #섬 번호 초기값
    n_isl =1
    
    #지도 전체를 돌면서 
    for i in range(N):
        for j in range(N):
        	#육지를 발견하고 해당 좌표를 방문하지 않았다면
            if l[i][j] == 1 and visited[i][j] == False:
                #재귀 DFS 실행
                rdfs(i,j,n_isl)
                #위 과정으로 부터 하나의 섬을 다 찾으므로 번호를 +1 시켜준다.
                n_isl+=1
    return n_isl




from collections import deque

def bfs(l,z): # l: 지도 z: 섬 번호
    """ 섬 사이의 최단거리를 찾아주는 BFS"""
    border = deque([])
    global ans
    dist = [[-1] * N for _ in range(N)] #거리를 측정할 리스트
    for i in range(N):
        for j in range(N):
            if l[i][j] == z: #특정 섬만 border에 담는다.
                 border.append([i, j])
                 dist[i][j] =0 # 시작점으로 기록

    while(border):
        x, y = border.popleft() #border에서 하나씩 꺼내서
        for k in range(4): #상하좌우로 움직였을 때
            nx = x + dx[k]
            ny = y + dy[k]
            if 0 <= nx < N and 0 <= ny < N: #지도 범위안에 있고
                if l[nx][ny] == 0 and dist[nx][ny] ==-1: #해당 좌표가 바다라면
                    dist[nx][ny] = dist[x][y] +1 #그전까지 최단거리에 +1
                    border.append([nx,ny])

                if  l[nx][ny] !=0 and l[nx][ny] !=z: #다른 섬에 도착했다면
                    ans = min(ans, dist[x][y]) #최소값을  비교해 저장
                    return ans
import sys
sys.setrecursionlimit(10**6)

N= int(input())
l = [list(map(int, input().split())) for i in range(N)]
visited =[[False for i in range(N)] for i in range(N)]


#전체 섬의 개수를 찾는다.
n_isl=dfs(l,visited)

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

ans=9999999
for i in range(1,n_isl):
    ans= min(ans,bfs(l,i))
print(ans)