문제

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

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

설명1

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

설명2

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

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

www.acmicpc.net/problem/2146

  • 입력

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

  • 출력

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

과정

역대급으로 어려운 문제였다😰.

일단 섬의 개수 문제가 떠올라서 이 문제에서도 섬을 넘버링 해야한다는 것까지는 생각했다.

그래서 bfs_island 함수에서는 섬을 넘버링하고 bfs_bridge 함수에서는 각각의 섬을 다시 bfs해서 다른 섬까지의 다리 길이를 구한 다음, 다리 길이의 최소값을 찾는 것으로 코드를 구현했다.

이 방법을 떠올렸을 때부터 너무 복잡해서 성공해도 시간 초과겠거니 했는데 역시 시간 초과였다.

import sys
import copy
from collections import deque

# 각각의 섬에 넘버링하는 함수
def bfs_island(q):
    global n, num
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or ny < 0 or nx >= n or ny >= n:
                continue
            elif arr[nx][ny] == 1:
                q.append([nx, ny])
                arr[nx][ny] = num

# 한 섬에서 다른 섬까지 bridge의 길이를 구하는 함수
def bfs_bridge(q, num, arr_tmp):
    global n, res, arr
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    # 새로운 배열에 현재 섬은 0, 바다는 -1로 기본값 설정
    for i in range(n):
        for j in range(n):
            if arr_tmp[i][j] == num:
                arr_tmp[i][j] = 0
            else:
                arr_tmp[i][j] = -1

    # bfs를 돌면서 다리의 길이를 구함
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or ny < 0 or nx >= n or ny >= n:
                continue
            elif arr_tmp[nx][ny] == -1:
                q.append([nx, ny])
                arr_tmp[nx][ny] = arr_tmp[x][y] + 1

    # 다른 섬까지의 최소 다리 길이를 구함
    for i in range(n):
        for j in range(n):
            if arr[i][j] > 0 and arr[i][j] != num:
                res = min(res, arr_tmp[i][j]-1)


n = int(sys.stdin.readline())
arr = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

# 섬 넘버링
num = 1
for i in range(n):
    for j in range(n):
        if arr[i][j] == 1:
            num += 1
            q = deque()
            q.append([i, j])
            bfs_island(q)

# 다리 길이의 최소 구하기
res = n + num
for k in range(2, num+1):
    q = deque()
    for i in range(n):
        for j in range(n):
            if arr[i][j] == k:
                q.append([i, j])
    bfs_bridge(q, k, copy.deepcopy(arr))

print(res)

괜히 arr 배열 하나로 모든 것을 해결하려다가 코드만 복잡해진 것 같다. 또 최소 다리 길이를 구하는 부분에서 쓸데없이 시간을 많이 잡아먹은듯 하다.

최종 코드

아래 코드는 내가 처음 작성한 코드와 접근법은 비슷하지만 훨씬 깔끔하다.

우선 배열을 두 개 더 사용했다. island 배열에는 섬들을 넘버링했고, 다리의 길이는 bridge 배열을 사용했다. 또 현재 섬에서 다른 섬을 만나면 바로 값을 반환하고, 현재 최소값(res)보다 다리 길이가 같거나 길어지면 굳이 더 이상 탐색을 진행하지 않는 방식으로 시간을 단축했다.

import sys
from collections import deque

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

# 각각의 섬에 넘버링하는 함수
def bfs_island(sx, sy):
    global n, cnt, island, dx, dy
    q = deque()
    q.append([sx, sy])
    island[sx][sy] = cnt

    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or ny < 0 or nx >= n or ny >= n:
                continue
            # 섬이고 and 방문하지 않았다면 q에 넣고 섬 넘버링
            elif arr[nx][ny] == 1 and island[nx][ny] == 0:
                q.append([nx, ny])
                island[nx][ny] = cnt

# 한 섬에서 다른 섬까지 bridge의 길이를 구하는 함수
def bfs_bridge(num):
    global n, q, arr, island, bridge, res, dx, dy

    while q:
        x, y = q.popleft()
        # 현재 다리의 길이보다 크거나 같다면 더 이상 구할 필요가 없으므로 넘긴다.
        if bridge[x][y] >= res:
            continue
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or ny < 0 or nx >= n or ny >= n:
                continue
            # 이 타일이 섬이고 and 다른 섬이라면 현재 다리의 길이를 반환
            elif arr[nx][ny] == 1 and island[nx][ny] != num:
                return bridge[x][y]
            # 이 타일이 바다이고 and 방문하지 않았다면 q에 넣고 다리의 길이를 업데이트
            elif arr[nx][ny] == 0 and bridge[nx][ny] == -1:
                q.append([nx, ny])
                bridge[nx][ny] = bridge[x][y] + 1
    return res

n = int(sys.stdin.readline())
arr = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
island = [[0]*n for _ in range(n)]
cnt = 1

# 섬 넘버링
for i in range(n):
    for j in range(n):
        if arr[i][j] == 1 and island[i][j] == 0:
            bfs_island(i, j)
            cnt += 1

# 섬의 개수 cnt만큼 반복문을 돌면서 각 섬에서부터 다른 섬까지의 최소 다리 길이를 구한다.
res = n*2
for k in range(1, cnt):
    q = deque()
    bridge = [[-1]*n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            # 이 타일이 k번째 섬이라면 q에 넣는다
            if island[i][j] == k:
                q.append([i, j])
                bridge[i][j] = 0
    res = min(res, bfs_bridge(k))

print(res)

Enhanced

개인적으로 이해하기에는 위의 코드가 더 쉽고 좋았지만 시간은 이 코드가 훨씬 더 짧았다.

여기서는 각각의 섬마다 bfs를 돌려서 다리의 길이를 구하는 것이 아니라 모든 섬들을 동시에 bfs를 돌려서 최소값을 찾았다. 섬들을 동시에 간척하는 것으로 비유할 수 있겠다.

각 섬들을 bfs를 통해 동시에 간척하다가 다른 섬과 만나면 현재 loop의 횟수를 통해 다리의 길이를 구하는 것이다.

여기서는 ocean이라는 큐를 사용하는데 bfs_island 함수에서 각 섬의 가장자리 타일을 저장해놓고 bfs_bridge 함수에서 사용한다.

더 이상 직접 설명하긴 어렵고 맨 아래 참고 사이트에 들어가보면 그림/표로 설명이 잘 되어있다.

import sys
from collections import deque

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

# 각각의 섬에 넘버링하는 함수
def bfs_island(sx, sy):
    global n, cnt, island, dx, dy
    q = deque()
    q.append([sx, sy])
    island[sx][sy] = cnt

    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or ny < 0 or nx >= n or ny >= n:
                continue
            # 섬이고 and 방문하지 않았다면 q에 넣고 섬 넘버링
            elif arr[nx][ny] == 1 and island[nx][ny] == 0:
                q.append([nx, ny])
                island[nx][ny] = cnt
            # 방문하지 않은 섬의 가장자리 타일이라면 ocean에 넣는다
            elif arr[nx][ny] == 0 and not [x, y] in ocean:
                ocean.append([x, y])

# 한 섬에서 다른 섬까지 bridge의 길이를 구하는 함수, 모든 섬에서 동시에 bfs를 실시한다
def bfs_bridge():
    global n, ocean, arr, island, dx, dy
    res = n*2
    loop = 0
    while ocean:
        loop += 1
        oceanlen = len(ocean)
        while oceanlen:
            x, y = ocean.popleft()
            oceanlen -= 1
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if nx < 0 or ny < 0 or nx >= n or ny >= n:
                    continue
                # 바다 타일이면 간척하고 ocean에 넣는다
                elif island[nx][ny] == 0:
                    island[nx][ny] = island[x][y]
                    ocean.append([nx, ny])
                # 간척을 하다가 현재 섬 타일보다 숫자가 큰 섬을 만난 경우
                elif island[nx][ny] > island[x][y]:
                    res = min(res, (loop - 1) * 2)
                # 간척을 하다가 현재 섬 타일보다 숫자가 작은 섬을 만난 경우
                elif island[nx][ny] < island[x][y]:
                    res = min(res, loop * 2 - 1)
    return res

n = int(sys.stdin.readline())
arr = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
island = [[0]*n for _ in range(n)]
cnt = 1
ocean = deque()

# 섬 넘버링
for i in range(n):
    for j in range(n):
        if arr[i][j] == 1 and island[i][j] == 0:
            bfs_island(i, j)
            cnt += 1

print(bfs_bridge())

참고 사이트