[BOJ] 2146. 다리 만들기(🥇, BFS)

문제

풀이

1. 섬을 구분하기 위해 각각의 섬을 찾아서 번호를 붙인다
2. 각 섬에서 bfs로 탐색하여 다른 섬을 찾으면 그 거리가 최단거리

1. 각 섬에 번호 붙이기

배열의 처음부터 끝까지 돌면서 섬을 발견하면 bfs로 탐색해서 연결된 모든 섬을 찾아 같은 번호를 붙여준다. 1번 섬을 찾고 나면 2번 섬을 찾는 방식...

이 다음에 각각의 섬에서 출발해서 다른 섬을 찾아야 하기 때문에 찾은 섬들은 딕셔너리에 섬의 번호를 키 값으로 하여 저장한다(land)

# 각각의 섬에 번호 붙이기
def findLand(x, y, z):
    global land
    visited[x][y] = z
    land[z] = [(x, y, 0)]
    q = [(x, y)]

    while q:
        x, y = q.pop(0)

        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if nx<0 or ny<0 or nx>=N or ny>=N or not arr[nx][ny] or visited[nx][ny]:
                continue

            visited[nx][ny] = z
            land[z].append((nx, ny, 0))
            q.append((nx, ny))
            
z = 1
for i in range(N):
    for j in range(N):
        if arr[i][j] and not visited[i][j]:
            findLand(i, j, z)
            z += 1

2. 다른 섬 찾기

번호 순서대로 각각의 섬에서 출발해서 다른 섬을 찾는 함수
섬을 찾기 위해서는 바다를 반드시 한 번이라도 거쳐야 하기 때문에 bfs로 탐색해서 만일 발견한 곳이 섬인데 같은 번호인 곳이라면 넘어가고, 바다라면 무조건 큐에 넣어서 탐색을 계속 진행한다. 이때 길이를 알아야 하기 때문에 cnt 변수를 추가하여 1씩 증가시킨다.

계속 진행하다가 육지를 만났는데 섬의 번호가 다른 곳이라면 최단거리를 찾은 것이므로 함수는 종료된다.

쉽게 말해 육지에선 바다를 찾고, 바다에선 다른 번호를 가진 육지를 찾으면 됨

# 각 섬에 땅에 대해서 땅에선 0을 찾고 0에선 다른 땅을 찾는 거
def putBridge(n, q):
    while q:
        x, y, cnt = q.pop(0)

        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if nx<0 or ny<0 or nx>=N or ny>=N or visited[nx][ny] == n:
                continue
            
            # 방문한 곳이 바다라면 q에 추가
            if not arr[nx][ny]:
                visited[nx][ny] = n
                q.append((nx, ny, cnt+1))
        
            # 방문한 곳이 바다가 아니라면 새로운 육지이니까 
            elif arr[nx][ny]:
                return cnt

최종코드

# 76ms

# 각각의 섬에 번호 붙이기
def findLand(x, y, z):
    global land
    visited[x][y] = z
    land[z] = [(x, y, 0)]
    q = [(x, y)]

    while q:
        x, y = q.pop(0)

        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if nx<0 or ny<0 or nx>=N or ny>=N or not arr[nx][ny] or visited[nx][ny]:
                continue

            visited[nx][ny] = z
            land[z].append((nx, ny, 0))
            q.append((nx, ny))

# 각 섬에 땅에 대해서 땅에선 0을 찾고 0에선 다른 땅을 찾는 거
def putBridge(n, q):
    while q:
        x, y, cnt = q.pop(0)

        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if nx<0 or ny<0 or nx>=N or ny>=N or visited[nx][ny] == n:
                continue
            
            # 방문한 곳이 바다라면 q에 추가
            if not arr[nx][ny]:
                visited[nx][ny] = n
                q.append((nx, ny, cnt+1))
        
            # 방문한 곳이 바다가 아니라면 새로운 육지이니까 
            elif arr[nx][ny]:
                return cnt
            

N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]
visited = [[0] * N for _ in range(N)]
land = {}
dx = (0, 1, 0, -1)
dy = (1, 0, -1, 0)

z = 1
for i in range(N):
    for j in range(N):
        if arr[i][j] and not visited[i][j]:
            findLand(i, j, z)
            z += 1

minLen = N*N
for num, lst in land.items():
    minLen = min(minLen, putBridge(num, lst))

print(minLen)