[백준 #2146] 다리 만들기 (Python)

말하는 감자·2023년 3월 23일

백준

목록 보기

5/6

[Gold III] 다리 만들기 - 2146

문제 링크

분류

그래프 이론, 그래프 탐색, 너비 우선 탐색

문제 설명

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

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

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

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

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

문제풀이

문제 풀이 아이디어

나라를 구분해서 입력을 주는 것이 아니기 때문에 각 나라를 구분해서 배열에 저장 시켜줘야한다.

백준에서 빙산(2573), 안전영역(2468)을 풀어보면 도움이 될듯?

bfs로 문제를 푸는 것이 바로 생각이 났고, 가장자리를 찾아야한다는 것을 알았다.

풀이 순서

지도에서 떨어져있는 나라를 구분하면서 visited배열에 저장한다.

나라를 번호로 1, 2, 3 ... visited배열에 저장

다리를 만들기 위해서는 가장자리에서 만들기 때문에 각 나라마다 가장자리를 찾는다.

가장자리의 x, y좌표를 2차원 배열에 인덱스(나라 번호)에 맞게 저장 시킨다.

각 가장자리에서 bfs를 하며 가장 짧은 다리를 만들 수 있는 상황에 다리의 길이를 갱신시킨다.

코드

from collections import deque
n = int(input())
Map = [list(map(int, input().split())) for _ in range(n)]
visited = [[0] * n for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# 나라를 번호별로 마킹하는 함수
def mark(i, j):
    q = deque()
    q.append((i, j))
    while q:
        x, y = q.popleft()
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if not(0 <= nx < n and 0 <= ny < n): continue
            if Map[nx][ny] == 0: continue
            if visited[nx][ny]: continue
            visited[nx][ny] = country
            q.append((nx, ny))

# 각 나라의 가장자리를 찾는 함수
def find_edge():
    edge = [set() for _ in range(country - 1)]
    for i in range(n):
        for j in range(n):
            if Map[i][j] == 0: continue
            for k in range(4):
                nx = i + dx[k]
                ny = j + dy[k]
                if not(0 <= nx < n and 0 <= ny < n): continue
                if Map[nx][ny] == 0:
                    edge[visited[i][j] - 1].add((i, j))
    return edge

# 다리를 만드는 함수
def make_bridge(i, j, num):
    global mn_bridge
    q = deque()
    q.append((i, j))
    bridge = [[0] * n for _ in range(n)]
    while q:
        x, y = q.popleft()
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if not(0 <= nx < n and 0 <= ny < n): continue
            if Map[nx][ny] != 0:
                if visited[nx][ny] != num:
                    mn_bridge = min(mn_bridge, bridge[x][y])
                    continue
            if bridge[nx][ny]: continue
            if visited[nx][ny] == country: continue
            bridge[nx][ny] = bridge[x][y] + 1
            q.append((nx, ny))


country = 1 # 각 나라 번호
for i in range(n):
    for j in range(n):
        if visited[i][j]: continue
        if Map[i][j] == 0: continue
        visited[i][j] = country
        mark(i, j)
        country += 1 # 한 나라의 마킹이 끝나면 나라 번호 증가
edge_lst = find_edge()

mn_bridge = 1e9
for i in edge_lst:
    for x, y in i:
        country = visited[x][y]
        make_bridge(x, y, country)
print(mn_bridge)