[백준 | 골드4] 2146_다리만들기(BFS, 떨어져있는 섬, 번호부여, 최단거리)

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

 

문제

2146번: 다리 만들기

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

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

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

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

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

입력

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

출력

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

예제 입력 1 복사

10
1 1 1 0 0 0 0 1 1 1
1 1 1 1 0 0 0 0 1 1
1 0 1 1 0 0 0 0 1 1
0 0 1 1 1 0 0 0 0 1
0 0 0 1 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 0 0 0 0
0 0 0 0 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0

예제 출력 1 복사

3

 

문제 요약
N * N 이차원 리스트
섬(1) 여러개 있고 바다(0)이 있다
두개의 섬을 연결하는 제일 짧은 다리리 한개의 거리를 구해라

문제 해설

문제풀이 전략
섬과 섬의 최단 거리를 구해라
1. 섬을 먼저 각각 구분해야한다.
- BFS를 한번 쭉 돈 다음 섬에 번호를 부여한다.
2. 4방향 탐색, 바다(0)이 있는 방문을 할수있다.
- 바다(0)인 경우 distance를 +1 증가시킨다
- distance를 체크하여 최소값을 갱신해야한다.

 

import sys
from collections import deque
sys.stdin = open("20220715_백준_2146_다리만들기.txt", "r")

n = int(input())
map_data = [list(map(int, input().split())) for _ in range(n)]
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
answer = sys.maxsize

#섬의 번호 구분
def BFS_separate(start_x, start_y, map_data, number) :
    dq = deque()

    #1인 시작점 넣기, 섬의 번호를 나누기 위해서 보드에 체크
    dq.append((start_x, start_y))
    map_data[start_x][start_y] = number     #섬에 번호 부여

    while dq :
        now_x, now_y = dq.popleft()

        #4방향 탐색
        for d in range(4):
            next_x = now_x + dx[d]
            next_y = now_y + dy[d]

            #범위 내에 있을 때 섬(1)만 방문해서 number로 변경
            #1인곳만 방문할것이다!
            if 0 <= next_x < n and 0 <= next_y < n and map_data[next_x][next_y] == 1:
                map_data[next_x][next_y] = number       #섬(1)에 섬 번호(number) 부여
                dq.append((next_x, next_y))

#섬이 번호로 구분되어 진 현재 경우 섬 번호(iland)와 다른 섬의 번호의 거리를 찾는다
def BFS_short(start_x, start_y, map_data, iland) :
    global answer
    dq = deque()
    distance_list = [[-1] * n for _ in range(n)]         #거리 저장 리스트 생성

    dq.append((start_x, start_y))                       #큐에 시작점 추가
    distance_list[start_x][start_y] = 0                 #현재 시작점을 다시 방문하지 않기 위해서 0으로 변경

    while dq :
        now_x, now_y = dq.popleft()

        for d in range(4) :
            next_x = now_x + dx[d]
            next_y = now_y + dy[d]

            if 0 <= next_x < n and 0 <= next_y < n :
                # 다른 땅을 만나면 기존 답과 비교하여 짧은 거리 선택
                #거리가 -1(거리 미계산)과 0(현재섬 출발점)이 아닌경우, 현재 섬 번호(iland)가 아닌 경우 최소 거리값 체크
                if map_data[next_x][next_y] > 0 and map_data[next_x][next_y] != iland :
                    answer = min(answer, distance_list[now_x][now_y])       #최소 거리 갱신
                    return

                #바다(0)인 경우 distance를 1씩 늘린다.
                if map_data[next_x][next_y] == 0 and distance_list[next_x][next_y] == -1 :
                    distance_list[next_x][next_y] = distance_list[now_x][now_y] + 1
                    dq.append((next_x, next_y))



def solution(n, map_data) :
    global answer
    number = 2
    
    #1. 각 섬을 구분하기 위해서 시작점인 1을 찾자, 그리고 섬의 번호(number)를 부여하자
    for i in range(n) :
        for j in range(n) :
            if map_data[i][j] == 1 :            #섬의 시작점을 하나 찾았다! number를 부여해보자
                BFS_separate(i, j, map_data, number)
                number += 1                     #섬에 부여할 번호 증가

    iland_count_end = number-1      #섬 부여번호는 1부터 iland_num까지

    #2. 섬의 번호가 부여되어 섬을 구분할 수 았다.
    #- 섬을 구분하고 바다의 거리를 구하여 거리를 측정한다.
    #- 다시 BFS 시작
    for iland in range(1, iland_count_end+1) :              #섬의 번호의 좌표가 시작점이 된다.
        for i in range(n) : 
            for j in range(n) :
                if map_data[i][j] == iland :                #0아닌 섬 번호가 시작점
                    BFS_short(i, j, map_data, iland)
    
    return answer

print(solution(n, map_data))