파이썬) 다리 만들기 - BOJ

https://www.acmicpc.net/problem/2146

import sys
from collections import deque

input = sys.stdin.readline

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


# 섬을 구분해주는 bfs
def bfs1(i, j):
    global count
    q = deque()
    q.append([i, j])
    vis[i][j] = True
    arr[i][j] = count

    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 arr[nx][ny] == 1 and not vis[nx][ny]:
                vis[nx][ny] = True
                arr[nx][ny] = count
                q.append([nx, ny])

# 바다를 건너며 가장 짧은 거리를 구한다.
def bfs2(z):
    global answer
    dist = [[-1] * n for _ in range(n)] # 거리가 저장될 배열
    q = deque()

    for i in range(n):
        for j in range(n):
            if arr[i][j] == z:
                q.append([i, j])
                dist[i][j] = 0

    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 갈 수 없는 곳이면 continue
            if nx < 0 or nx >= n or ny < 0 or ny >= n:
                continue
            # 다른 땅을 만나면 기존 답과 비교하여 짧은 거리 선택
            if arr[nx][ny] > 0 and arr[nx][ny] != z:
                answer = min(answer, dist[x][y])
                return
            # 바다를 만나면 dist를 1씩 늘린다.
            if arr[nx][ny] == 0 and dist[nx][ny] == -1:
                dist[nx][ny] = dist[x][y] + 1
                q.append([nx, ny])


n = int(input())

arr = [list(map(int, input().split())) for _ in range(n)]
vis = [[False] * n for _ in range(n)]
count = 1
answer = sys.maxsize

for i in range(n):
    for j in range(n):
        if not vis[i][j] and arr[i][j] == 1:
            bfs1(i, j)
            count += 1

# print(arr)

for i in range(1, count):
    bfs2(i)

print(answer)

 

요점은 두개다.

• 대륙을 나눈다
• 대륙에서 대륙사이의 최단 거리를 구한다.

1번은 간단하게 bfs로 구할 수 있지만 대륙간 최단 거리를 구하는 데에서 조금 많이 해맸다.

우선 대륙 내부의 숫자를 모두 한 숫자로 통일한다. 1번 대륙은 1로, 2번 대륙은 2로...

1번 대륙을 예로 들자면 1번 대륙의 i,j값을 큐에 담고 bfs를 실행한다

이때,

1. 만약 나와 같은 대륙이라면 큐에 담지 않는다( 왜냐하면 1번 대륙의 모든 i,j는 큐에 담아놨기 때문이다,)
2. 만약 바다라면 q에 담는다.
3. 바다를 큐에 담을 때 dist라는 리스트에 길이를 업데이트한다
4. 만약 1번 대륙과 다른 대륙이라면(2,3번 대륙이라면) answer의 값을 업데이트하고 종료시킨다.

이 조건만 지켜내면 아무런 문제없이 풀 수 있는 문제였다.

역시 알고리즘은 많이 풀어야하는게 실력을 빨리 늘릴 수 있는 유일한 길 같다.