[백준] [파이썬] [BFS] 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

---

전혀 풀지 못하였다.

이 문제는 2가지 과제를 수행해야한다.

1. 섬에서 자기 섬으로 다리를 놓는것을 방지하기 위해 섬끼리 구분해야한다.
2. 섬에서 섬으로 최단 다리를 구한다

1번 테스크는 섬 개수, 그림 개수, 그림 크기, 단지 문제와 같이 풀면 된다.
2번 테스크는 미로 최단거리문제처럼 최단 거리를 찾는다.
섬에서 섬을 돌면서 다른 섬을 만날 때까지 바다를 건너며 가장 짧은 길을 찾는다

---

BFS로 푼 방법

import sys 
from collections import deque 
sys.stdin=open('input.txt', 'r')
dx=[0,-1,0,1]
dy=[1,0,-1,0]

# 섬을 구분하기 위해 섬에 숫자를 부여한다 
def BFS1(i,j):
    global island 
    Q=deque()
    Q.append((i,j))
    visited[i][j]=1 
    board[i][j]=island
    while Q:
        x,y=Q.popleft()
        for k in range(4):
            nx=x+dx[k]
            ny=y+dy[k]
            if 0<=nx<N and 0<=ny<N and board[nx][ny]==1 and visited[nx][ny]==0:
                visited[nx][ny]=1
                board[nx][ny]=island
                Q.append((nx,ny))

def BFS2(island):
    global res 
    dis=[[-1]*N for _ in range(N)]      # 지도와 똑같은 크기의 거리 기록지, -1이라고 한 이유는 첫방문일때 -1인거 확인하려고 
    Q=deque()
    for i in range(N):
        for j in range(N):
            if board[i][j]==island:
                Q.append((i,j))         # 현재 확인할 섬의 모든 위치 Q에 넣음 
                dis[i][j]=0             # 현재 확인할 섬만 0으로 시작 설정 
    while Q: 
        x,y=Q.popleft()
        for k in range(4):
            nx=x+dx[k]
            ny=y+dy[k]
            if 0<=nx<N and 0<=ny<N:     # 지도 범위 안에서 
                # 바다가 아니면서 자기 섬아닌 경우. 즉, 현재 섬에서 새로운 땅인 경우 
                if board[nx][ny]!=0 and board[nx][ny]!=island: 
                    res=min(res,dis[x][y])
                    return
                # 바다면 다리 거리 1을 늘린다 
                if board[nx][ny]==0 and dis[nx][ny]==-1:
                    dis[nx][ny]=dis[x][y]+1 
                    Q.append((nx,ny))       # 바디위에서 다음 다리 위치 추가하며 다리를 건설

if __name__=="__main__":
    N=int(input())
    board=[list(map(int, input().split())) for _ in range(N)]
    visited=[[0]*N for _ in range(N)]

    res=sys.maxsize

    # 1. 섬을 구분하기 위해 그림 개수 문제 또는 그림 크기 문제 처럼 BFS를 수행한다  
    island=1
    for i in range(N):
        for j in range(N):
            if board[i][j]==1 and visited[i][j]==0: # 섬이면서 첫 방문
                BFS1(i,j)                            # 1번 섬, 이후에 2번 섬, 3번 섬....
                island+=1

    # 2. 섬별로 가장 짧은 다리 길이를 구하기 위해 BFS를 수행한다 
    for i in range(1,island):
        BFS2(i)

    print(res)

---

bfs를 연달아 두개 쓰는 방법이었는데 처음 보는 유형이어서 아이디어에 대한 생각이 많이 걸렸다.

이럴 때마다 알고리즘은 많이 푸는게 답이다 라는 것을 느끼게 되는 것 같다.

---

BFS를 연달아 두개 쓰는 방법이었는데 처음 보는 유형이어서 아이디어에 대한 생각이 많이 걸렸다.

이럴 때마다 알고리즘은 많이 푸는게 답이다 라는 것을 느끼게 되는 것 같다.