[백준] 2146 다리 만들기 (Python/파이썬)

<문제 링크>

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

2146번: 다리 만들기

<풀이 전략>

1. 기본 접근은 각각의 섬에 다른 번호를 부여하고 각각의 섬에 대해서 bfs를 통해서 다리의 최소 길이를 구하는 것이다.

2. 다만 메모리초과가 나기 쉬워서 visited배열을 잘 활용해야 한다. 나 같은 경우는 다리 건설하는 bfs 함수 안에 visited배열을 하나 만들고, 섬의 번호에 대한 visited배열을 하나 더 만들어서 한 번 탐색한 섬에 대해서 다시 탐색하지 않도록 했다.

3. 다리를 건설하기 위해서 섬 내부를 탐색할 때는 탐색하기 전에 미리 해당 섬 내부를 탐색해서 섬 내부의 영역을 방문처리하고 bfs 탐색을 실시했다.

 

<정답 코드>

from collections import deque
import sys, os, io, atexit

input = lambda: sys.stdin.readline().rstrip('\r\n')
stdout = io.BytesIO()
sys.stdout.write = lambda s: stdout.write(s.encode("ascii"))
atexit.register(lambda: os.write(1, stdout.getvalue()))

# 220927 2146 다리 만들기

# 정답코드

# 델타 탐색 방향 설정
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]


# 섬에 각각 번호를 부여하는 함수
def bfs_island(r, c, idx):
    # 방문 표시 및 번호 표시
    arr[r][c] = idx
    visited[r][c] = 1
    
    queue = deque()
    queue.append((r, c))
    
    while queue:
        r, c = queue.popleft()
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            if 0 <= nr < N and 0 <= nc < N:
                # 섬 내에 방문하지 않은 인접 육지가 있을 경우
                if visited[nr][nc] == 0 and arr[nr][nc] == 1:
                    # 번호 부여하고 방문 표시
                    arr[nr][nc] = idx
                    visited[nr][nc] = 1
                    
                    queue.append((nr, nc))

    return


# bfs로 다리 연결하는 함수
def bfs_bridge(r, c, island_num):
    # visited: 방문 여부 표시 배열
    visited = [[0 for _ in range(N)] for _ in range(N)]
    
    queue = deque()

    # 선택한 섬을 먼저 다 방문처리하고 큐에 넣어준다.
    for r in range(N):
        for c in range(N):
            if arr[r][c] == island_num:
                queue.append((r, c, 0))
                visited[r][c] = 1

    while queue:
        r, c, cnt = queue.popleft()
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            if 0 <= nr < N and 0 <= nc < N and visited[nr][nc] == 0:
                # 바다일 경우 다리 길이를 세주면서 탐색
                if arr[nr][nc] == 0:
                    visited[nr][nc] = 1
                    queue.append((nr, nc, cnt + 1))
                # 다른 섬을 만났을 경우 다리 길이 반환
                elif arr[nr][nc] != island_num: 
                    return cnt

# N: 배열의 크기, arr: 섬 배열
N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]

# idx: 섬의 번호, visited: 방문 여부 표시 배열(섬 번호 부여 시)
idx = 1
visited = [[0 for _ in range(N)] for _ in range(N)]
# 배열을 탐색하면서 섬에 번호를 부여해준다.
for r in range(N):
    for c in range(N):
        if arr[r][c] == 1 and visited[r][c] == 0:
            bfs_island(r, c, idx)
            # 하나의 섬을 탐색했을 경우 다음 번호
            idx += 1

# island_visited: 다리 건설 여부를 나타내는 배열
island_visited = [0 for _ in range(idx)]

# ans: 다리의 최소 길이 (충분히 큰 값으로 초기화)
ans = sys.maxsize
for r in range(N):
    for c in range(N):
        # 다리를 건설하지 않은 섬에 대해서 bfs로 다리 건설
        if arr[r][c] != 0 and island_visited[arr[r][c]] == 0:
            island_num = arr[r][c]
            island_visited[island_num] = 1
            # 최솟값 갱신
            ans = min(ans, bfs_bridge(r, c, island_num))

# 정답 출력
print(ans)