백준 2146번 - 다리 만들기

출처 : 2146번: 다리 만들기 (acmicpc.net)

2146번: 다리 만들기

---

다리 만들기 성공분류

시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율

2 초

192 MB

21390

7516

4715

33.060%

문제

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

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

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

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

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

입력

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

출력

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

---

[ 문제 설명 ]

 

어떤 섬이든 섬과 섬이 이어지는 다리의 최솟값을 구하는 문제.

자세한 설명은 그림으로 하겠습니다.

 

섬의 개수를 카운트해주는 코드는 백준 2667번 - 단지 번호 붙이기 (tistory.com) 참고하자.

 

그림 1 - 다리 만들기 설명

그림 2 - 다리 만들기 설명

그림 3 - 다리 만들기 설명

그림 1에서 보여주는 ex 부분 예시처럼 확장하는 방식으로 다리가 이어지는 최솟값을 구한다.

다만 이해를 돕기 위해 파란색 숫자로 [[1, 1, 2 ], [ 1, 2, 3], [2, 3, 3]]으로 표현했지만, 실제로는 (1,0) 좌표에서 다리가 이어질 때, 하나의 상황이 종료된다. 

그림 1 ex가 작동되는 방식으로 그림 2, 그림 3에서 코드 부분과 매칭 하여 설명했다.

 

코드 블록을 보겠다.

---

[ 코드 ]

 

from collections import deque
import sys

input = sys.stdin.readline
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

# 섬의 개수 새기
def findIslandBFS(x, y, cnt):
    q1.append([x, y])
    visited1[x][y] = cnt
    while q1:
        x, y = q1.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n:
                if maps[nx][ny] == 1 and visited1[nx][ny] == 0:
                    visited1[nx][ny] = cnt
                    q1.append([nx, ny])


def bfs2(num):
    while q1:
        x, y = q1.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n:
                if maps[nx][ny] == 1 and visited1[nx][ny] != num:
                    # 섬이 이어지는 다리의 개수 리턴, != num 이아니면 만난 경우로 그 다리수를 리턴해주는것
                    return visited2[x][y] - 1
                if maps[nx][ny] == 0 and visited2[nx][ny] == 0:
                    visited2[nx][ny] = visited2[x][y] + 1
                    q1.append([nx, ny])


n = int(input())
maps = [list(map(int, input().split())) for _ in range(n)]
visited1 = [[0] * n for _ in range(n)]
q1 = deque()

cnt = 1

# 섬의 개수를 찾는 시작 코드
for i in range(n):
    for j in range(n):
        if maps[i][j] == 1 and visited1[i][j] == 0:
            findIslandBFS(i, j, cnt)
            cnt += 1

# print(visited1)
ans = sys.maxsize
# print(ans)
for k in range(1, cnt):
    q1 = deque()
    visited2 = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if maps[i][j] == 1 and visited1[i][j] == k:
                q1.append([i, j])
                visited2[i][j] = 1

    #print("초기", visited2)

    # 섬을 선택해 넓히는 역할을 하는 함수 호출
    res = bfs2(k)
    #print("결과", visited2)
    # print(visited2[0][2])
    ans = min(ans, res)

# print(maps)
print(ans)

그림을 이해하셨다면, 어렵지 않게 이해가 되실 것. 이해가 안 되는 부분이 있다면 언제나 환영.

 

---

후기

 

조금씩 문제가 다르게 변형하면서 낸다는 느낌을 받는다.