백준 2146 파이썬 코드 답안

문제

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

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

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

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

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

입력

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

출력

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

문제 풀이

나는 이 문제를 BFS로 접근했다. 1달 전에 이 문제를 처음 풀었을 때는, BFS로 1과 0이 만나는 시점을 확인하고 최단거리를 어떻게든 구현해보려고 접근을 했으나, 당연하게도 내 구현력의 한계로 틀렸다. 한 달 후, 돌고 돌아 이 문제를 다시 만났을 때는 다른 방법으로 접근했다.

N은 100까지 주어지는데, 이 말인 즉슨 좌표는 10000까지 가능하다는 소리다. 예를 들어서, N이 100일 때, 섬이 3개로 나누어지고 그에 대한 좌표의 개수가 각각 3000,3000,4000개가 있다고 가정을 해본다. 여기서, 각 좌표를 비교해본다고 가정했을 때, 사용되는 경우의 수는 그리 많지 않을 것을 깨달았다.

3000 * (3000 + 4000) + 3000 * 4000으로 아무리 많아도 100만이 넘지 않는 것을 알았다. 즉, BFS로 섬을 구분지어두고, 각 섬의 좌표에 대해서 완전탐색으로 길이가 최소가 되는 좌표를 구해도 시간 초과 및 메모리 초과가 없을 것이란 것을 알게 되었다. 

따라서 문제는 크게 3등분해서 풀었다.

1. 입력을 받는다.
2. BFS를 전체 맵에 대해서 돌려서, 각 섬을 분류한다.
   이 때, 섬을 분류하면서 새로운 섬이 발견될 때 마다 새로운 섬에 대한 리스트를 추가해주고, 해당 리스트에 섬의 좌표를 입력했다.
3. 입력된 섬의 좌표를 바탕으로 다른 섬끼리 완전 탐색으로 좌표 비교를 통해 최소값을 잡는 방식으로 접근했다. 

코드는 아래와 같다.

 

import sys
from collections import deque

def bfs(y,x,inum) :
    que = deque()
    que.append([y,x])
    visit[y][x] = 1
    my_map[y][x] = inum
    island_li[inum].append([y,x])
    while que :
        y,x = que.popleft()
        for k in tra_list :
            next_y = y + k[0]
            next_x = x + k[1]
            if 0 < next_y < n+1 and 0 < next_x < n+1 :
                if visit[next_y][next_x] == 0 and my_map[next_y][next_x] == 1 :
                    visit[next_y][next_x] = 1
                    my_map[next_y][next_x] = inum
                    que.append([next_y,next_x])
                    island_li[inum].append([next_y,next_x])


tra_list = [[1,0],[0,1],[-1,0],[0,-1]]


n = int(sys.stdin.readline().rstrip())
my_map = [[0] for _ in range(n+1)]
visit = [ [0 for _ in range(n+1)] for _ in range(n+1)]
for i in range(1,n+1) :
    temp = list(map(int,sys.stdin.readline().split()))
    for k in temp :
        my_map[i].append(k)

island_li = [0,0]
p = 2
for i in range(1,n+1) :
    for j in range(1,n+1) :
        if my_map[i][j] == 1 :
            island_li.append([])
            bfs(i,j,p)
            p = p+1

answer = 500000
for i in range(2,len(island_li)) :
    for j in range(2,len(island_li)) :
        if i!=j :
            for x in island_li[i] :
                for y in island_li[j] :
                    temp = abs(x[0] - y[0]) + abs(x[1] - y[1]) -1
                    answer = min(temp,answer)


print(answer)