[파이썬][백준 2146][💛골드 3] 다리 만들기 (BFS)

🧞‍♂️‍ 난이도

💛 골드 3

🧞‍♂️ 문제

다리 만들기

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

🧞‍♂️ 내 풀이

내가 문제를 접근한 과정은 다음과 같다.

1. 각 섬을 색칠하자.
   • 땅을 의미하는 “1” 대신에 각 땅덩어리에 고유 식별자를 정해서 저장한다.
   • 그럼 첫번째 땅덩어리는 전부 1, 두번째는 2, 세번째는 3..이런식으로 식별이 가능해진다.
   • 이렇게 해주는 이유는, 땅덩어리->다른 땅덩어리 에 다리를 만드는 경로를 BFS로 탐색할건데, 하나의 땅덩어리에서 탐색을 시작해서, 다시 자기 자신한테 오는 경로를 방지하기 위함이다.
   • 즉, 이어진 두개의 땅덩어리의 식별자가 달라야만 유효한 다리로 간주하는 논리이다.
2. 각 섬의 가장 가장자리에 있는 땅을 저장하다
   • 각 섬의 가장자리 땅에서 BFS 를 전부 한번씩 돌려서, 최소 다리를 찾을것이다.

🧞‍♂️ 후기

접근 방법은 바로 떠올랐고 구현도 꽤 빠르게 했었는데, visited[src_x][src_y] 를 visited[src_y][src_y] 로 해서 틀리고 섬을 색칠하는걸 처음에 DFS 로 했었는데, recursion error 이 발생했다. 섬을 색칠하는것도 BFS 로 해야 통과가 된다.

🧞‍♂️ 배운점

BFS 로 다리 경로 탐색을 할때, 처음에는 최소 다리를 BFS 안에서도 기록하고 리턴해야되는걸로 착각했었다. 근데 생각해보니까, 너비우선탐색 의 원리는 가장 근접한 곳부터 탐색을 하기 때문에, 먼저 다른 땅에 닿는 경로가 최소가 되는것이라 굳이 min_bridge = min(min_bridge, bridge) 로 최소 다리를 기록할 필요가 없다.

🧞‍♂️ 파이썬 코드

import sys, collections
N = int(input())
board = [input().split() for _ in range(N)]

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
edges = collections.defaultdict(set)

def markIslands(src_x, src_y, marker):
    visited = [[False] * N for _ in range(N)]
    visited[src_x][src_y] = True
    board[src_x][src_y] = marker
    q = collections.deque()
    q.append([src_x, src_y])
    while q:
        cur_x, cur_y = q.popleft()
        for i in range(4):
            nx, ny = cur_x + dx[i], cur_y + dy[i]
            if 0 <= nx < N and 0 <= ny < N and not visited[nx][ny]:
                if board[nx][ny] == '0':
                    edges[marker].add((cur_x, cur_y))
                else:
                    board[nx][ny] = marker
                    visited[nx][ny] = True
                    q.append([nx, ny])

# island 표시
visited = [[False] * N for _ in range(N)]
marker = 1
for x in range(N):
    for y in range(N):
        if board[x][y] == '1':
            markIslands(x,y,marker) 
            marker += 1

# 다리 탐색
def bfs(src_x, src_y, islandNum):
    visited = [[False] * N for _ in range(N)]
    visited[src_x][src_y] = True
    q = collections.deque()
    q.append([src_x, src_y, 0])
    while q:
        cur_x, cur_y, bridgeLength = q.popleft()
        for i in range(4):
            nx, ny = cur_x + dx[i], cur_y + dy[i]
            if 0 <= nx < N and 0 <= ny < N and not visited[nx][ny]:
                visited[nx][ny] = True
                if board[nx][ny] != '0' and board[nx][ny] != islandNum:
                    return bridgeLength
                else:
                    q.append([nx, ny, bridgeLength + 1])

test = collections.defaultdict(list)
answer = float('inf')
for islandNum in edges:
    for x, y in edges[islandNum]:
        answer = min(answer, bfs(x, y, islandNum))
print(answer)

---

맨 위로 이동하기

BOJ 카테고리 내 다른 글 보러가기