집념의 우경 ,,진짜 넘 어려워서 눈물 줄줄,, 까먹기 전에 복기하기,,

문제 링크

다리만들기 2

문제 설명

N*M크기의 지도 위에 섬으로 이루어진 나라가 표시된다. 격자의 각 칸은 땅이거나 바다인데, 다리를 연결해서 모든 섬을 연결하려고 한다.
다리는

• 바다에만 설치가 가능
• 길이가 2 이상이어야함
• 한 다리의 방향이 중간에 바뀌면 안됨 -> 다리의 방향은 가로/세로

나라의 정보가 주어졌을 때, 모든 섬을 연결하는 다리 길이의 최솟값을 구해보자.

문제 풀이

테스트 케이스 1을 예로 들면,

7 8
0 0 0 0 0 0 1 1
1 1 0 0 0 0 1 1
1 1 0 0 0 0 0 0
1 1 0 0 0 1 1 0
0 0 0 0 0 1 1 0
0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1

1. BFS를 이용해서 각각의 섬을 구분한다
   위의 테스트 케이스의 경우에는

   0, 0, 0, 0, 0, 0, 2, 2
   3, 3, 0, 0, 0, 0, 2, 2
   3, 3, 0, 0, 0, 0, 0, 0
   3, 3, 0, 0, 0, 4, 4, 0
   0, 0, 0, 0, 0, 4, 4, 0
   0, 0, 0, 0, 0, 0, 0, 0
   5, 5, 5, 5, 5, 5, 5, 5

def find_island(x, y, num):
    queue = deque([(x, y)])
    board[x][y] = num

    while queue:
        x, y = queue.popleft()

        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if in_range(nx, ny) and board[nx][ny] == 1:
                board[nx][ny] = num
                queue.append((nx,ny))

2. BFS를 이용해서 섬끼리 연결할 수 있는 다리의 경우를 구한다.
   위의 테스트 케이스의 경우에는

   {(2, 3): 4, (2, 5): 4, (3, 5): 2, (3, 4): 3}

def find_bridge(islandnum, x, y):
    queue = deque([(x, y, 0, 0), (x, y, 1, 0), (x, y, 2, 0), (x, y, 3, 0)])
    visited = [[False]*m for _ in range(n)]

    while queue:
        #한방향으로만 쭉 이동
        x, y, dir, count = queue.popleft()

        nx, ny = x+dx[dir], y+dy[dir]
        if in_range(nx, ny) and not visited[nx][ny]:
            #바다면
            if board[nx][ny] == 0:
                queue.append((nx, ny, dir, count+1))
            #다른 섬이면
            elif board[nx][ny] != islandnum:
                if count > 1:
                    is_a = min(board[nx][ny], islandnum)
                    is_b = max(board[nx][ny], islandnum)
                    if (is_a, is_b) in distance.keys():
                        distance[(is_a, is_b)] = min(distance[(is_a, is_b)], count)
                    else:
                        distance[(is_a, is_b)] = count

3. 크루스칼 알고리즘을 이용해서 MST를 만들 수 있는지 검사!
   2에서 구한 각각의 다리에 대해서, 연결할 수 있는 간선이 섬의 개수-1이면 MST를 만들 수 있고, 아니면 만들 수 없으니까 -1을 출력한다.

for edge in edges:
    cost, (a, b) = edge
    if find_parent(parent, a) != find_parent(parent, b):
        union_parent(parent, a, b)
        result += cost

전체 코드

import sys
from collections import deque, defaultdict

input = sys.stdin.readline
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

n, m = map(int, input().split())
board = []
for _ in range(n):
    board.append(list(map(int, input().split())))

def in_range(x, y):
    if x in range(n) and y in range(m):
        return True
    return False

def find_island(x, y, num):
    queue = deque([(x, y)])
    board[x][y] = num

    while queue:
        x, y = queue.popleft()

        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if in_range(nx, ny) and board[nx][ny] == 1:
                board[nx][ny] = num
                queue.append((nx,ny))

def next_to_sea(x, y):
    for i in range(4):
        nx, ny = x+dx[i], y+dy[i]
        if in_range(nx, ny) and board[nx][ny] == 0:
            return True
    return False

def find_bridge(islandnum, x, y):
    queue = deque([(x, y, 0, 0), (x, y, 1, 0), (x, y, 2, 0), (x, y, 3, 0)])
    visited = [[False]*m for _ in range(n)]

    while queue:
        #한방향으로만 쭉 이동
        x, y, dir, count = queue.popleft()

        nx, ny = x+dx[dir], y+dy[dir]
        if in_range(nx, ny) and not visited[nx][ny]:
            #바다면
            if board[nx][ny] == 0:
                queue.append((nx, ny, dir, count+1))
            #다른 섬이면
            elif board[nx][ny] != islandnum:
                if count > 1:
                    is_a = min(board[nx][ny], islandnum)
                    is_b = max(board[nx][ny], islandnum)
                    if (is_a, is_b) in distance.keys():
                        distance[(is_a, is_b)] = min(distance[(is_a, is_b)], count)
                    else:
                        distance[(is_a, is_b)] = count

def find_parent(parent, x):
    # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

# 두 원소가 속한 집합을 합치기
def union_parent(parent, a, b):
    global connected
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b
    connected += 1
    
                
# 섬끼리 구분짓기
num = 2
for i in range(n):
    for j in range(m):
        if board[i][j] == 1:
            find_island(i, j, num)
            num += 1
distance = {}
#섬끼리 연결하기
for i in range(n):
    for j in range(m):
        #땅이면
        if board[i][j] != 0 and next_to_sea(i,j):
            #바다 옆이면
            find_bridge(board[i][j], i, j)

# 크루스칼로 섬들끼리 연결하는 최소 비용 찾기
edges = []
connected = 0
result = 0
parent = [0] * num

for i in range(1, num):
    parent[i] = i

for key, val in distance.items():
    edges.append((val, key))

edges.sort()

for edge in edges:
    cost, (a, b) = edge
    if find_parent(parent, a) != find_parent(parent, b):
        union_parent(parent, a, b)
        result += cost


if connected == num -3:
    print(result)
else:
    print(-1)

느낀점

풀이 방법은 금방 떠올렸는데 아직 크루스칼 알고리즘이 안익숙해서 그런지,, MST찾는 부분이 어려웠다 아주 마니,,