[백준17472/골드1] 다리 만들기 2 - Python

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

 

 

✅ 문제 조건

1. 다리의 방향은 가로 또는 세로로만 연결 가능하다
2. 방향이 가로인 다리는 다리의 양 끝이 가로방향으로 섬과 인접, 세로도 마찬가지
3. 다리의 길이는 2 이상
4. 다리 교차 가능
5. 모든 섬이 연결하는 다리 길이의 최솟값 구하기

 

✅ 접근 방법

 

1. 섬 위치 체크

BFS를 이용해 하나의 섬마다 고유 번호를 부여하고, 바다와 맞닿아 있는 가장자리 좌표를 따로 저장했다.

여기까지는 다리만들기1이랑 거의 비슷하게 풀었다.

 

2. 섬의 가장자리만 모아둔 배열에서 다른 섬까지 한 방향으로 다리 만들어 나가기

가장자리 좌표에서 상하좌우 한 방향으로 쭉 탐색하고, 다른 섬에 도달 가능한 경우 다리 후보로 저장한다.
이때 다리 길이가 2 이상을 체크해줘야한다.

 

3. 길이가 가장 짧은 다리 우선순위로 다리 연결

길이 기준으로 정렬한 다리 후보를 차례대로 연결하고, 유니온 파인드를 사용해서 다리가 이어져있는지 체크한다.

 

 

✅ 구현

1. 섬 번호 매기기 + 가장자리 추출

def mark_island(x, y, island_id):
    q = deque([(x, y)])
    visited[x][y] = True
    mp[x][y] = island_id

    while q:
        cx, cy = q.popleft()

        for dx, dy in directions:
            nx, ny = cx + dx, cy + dy

            if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny]:
                    if mp[nx][ny] == 1:
                        visited[nx][ny] = True
                        mp[nx][ny] = island_id
                        q.append((nx, ny))
                    elif mp[nx][ny] == 0:
                        island_edges.append((cx, cy, island_id))
            
island_id = 2  # 섬 번호는 2부터 시작
for i in range(N):
    for j in range(M):
        if not visited[i][j] and mp[i][j] == 1:
            mark_island(i, j, island_id)
            island_id += 1

 

2. 한 방향으로 다리 만들기

def build_bridge(x, y, island_id, direction_index):
    dx, dy = directions[direction_index]
    length = 0
    nx, ny = x + dx, y + dy

    while 0 <= nx < N and 0 <= ny < M:
        if mp[nx][ny] == island_id:  # 자기 섬 만나면 중단
            break
        if mp[nx][ny] != 0 and mp[nx][ny] != island_id:  # 다른 섬 만나면 후보에 넣은 후 중단
            if length >= 2:
                bridges.append((length, island_id, mp[nx][ny]))
            break
        # 바다인 경우 계속 진행
        length += 1
        nx += dx
        ny += dy

for x, y, id in island_edges:
    for d in range(4):
        build_bridge(x, y, id, d)

 

3. 크루스칼을 위한 유니온 파인드

parent = [i for i in range(island_id)]

def find(a):
    if parent[a] != a:
        parent[a] = find(parent[a])
    return parent[a]

def union(a, b):
    a_root = find(a)
    b_root = find(b)
    if a_root != b_root:
        if a_root < b_root:
            parent[b_root] = a_root
        else:
            parent[a_root] = b_root

# 다리 길이가 짧은 순으로 이어져있지 않은 다리 연결
bridges.sort()
total_length = 0
connection_count = 0

for length, a, b in bridges:
    if find(a) != find(b):
        union(a, b)
        total_length += length
        connection_count += 1

# 모든 섬이 연결되어 있으면 길이 출력
roots = set(find(i) for i in range(2, island_id))
print(total_length if len(roots) == 1 else -1)

 

3. 최종 코드

'''
다리 연결 방법
1. 다리의 방향은 가로 또는 세로로만 연결 가능하다
2. 방향이 가로인 다리는 다리의 양 끝이 가로방향으로 섬과 인접, 세로도 마찬가지
3. 다리의 길이는 2 이상
4. 다리 교차 가능
5. 모든 섬이 연결하는 다리 길이의 최솟값 구하기
풀이
1. 섬의 테두리부분 전부 저장
    섬인 부분 (1) bfs로 탐색하며
    a. 주변이 같은 섬일 경우 q에 추가
    b. 주면이 같은 섬이 아닐 경우 island에 추가 (섬 번호 cnt 부여)
2. 그 섬 테두리에서 하나씩 꺼내서 상하좌우 탐색
    a. 한 방향으로만 탐색하며다른 섬에 도착했을 경우 섬 후보에 append(length, num1, num2)
    b. 다른 섬에 도착하지 못하는 경우 break
3. 섬 후보 중에서 다리 선택
    a. 후보 길이순으로 정렬
    b. 다리 하나 꺼내서 시작과 끝 다리 연결 (union)
4. 다리 연결 후 하나로 이루어져 있는지 검사 (find)
'''
from collections import deque

N, M = map(int, input().split())
mp = [list(map(int, input().split())) for _ in range(N)]
directions = [(-1, 0), (1, 0), (0, 1), (0, -1)]

visited = [[False] * M for _ in range(N)]
island_edges = deque()  # 섬의 가장자리 좌표들 저장
bridges = []            # 가능한 다리 후보들 저장

# 1. 하나의 섬을 탐색하여 번호를 붙이고, 가장자리를 저장
def mark_island(x, y, island_id):
    q = deque([(x, y)])
    visited[x][y] = True
    mp[x][y] = island_id

    while q:
        cx, cy = q.popleft()
        is_edge = False

        for dx, dy in directions:
            nx, ny = cx + dx, cy + dy

            if 0 <= nx < N and 0 <= ny < M:
                if not visited[nx][ny]:
                    if mp[nx][ny] == 1:
                        visited[nx][ny] = True
                        mp[nx][ny] = island_id
                        q.append((nx, ny))
                    elif mp[nx][ny] == 0:
                        is_edge = True
            else:
                is_edge = True  # 가장자리 체크

        if is_edge:
            island_edges.append((cx, cy, island_id))

# 2. 한 방향으로만 다리를 건설하며 다른 섬에 도달할 수 있는지 확인
def build_bridge(x, y, island_id, direction_index):
    dx, dy = directions[direction_index]
    length = 0
    nx, ny = x + dx, y + dy

    while 0 <= nx < N and 0 <= ny < M:
        if mp[nx][ny] == island_id:  # 자기 섬 만나면 중단
            break
        if mp[nx][ny] != 0 and mp[nx][ny] != island_id:
            if length >= 2:
                bridges.append((length, island_id, mp[nx][ny]))
            break
        # 바다인 경우 계속 진행
        length += 1
        nx += dx
        ny += dy

# 3. 모든 섬을 탐색하면서 번호 부여 및 가장자리 수집
island_id = 2  # 섬 번호는 2부터 시작
for i in range(N):
    for j in range(M):
        if not visited[i][j] and mp[i][j] == 1:
            mark_island(i, j, island_id)
            island_id += 1

# 4. 각 가장자리에서 다리 건설 시도
for x, y, id in island_edges:
    for d in range(4):
        build_bridge(x, y, id, d)

# 5. Union-Find 구조로 MST 구성
parent = [i for i in range(island_id)]

def find(a):
    if parent[a] != a:
        parent[a] = find(parent[a])
    return parent[a]

def union(a, b):
    a_root = find(a)
    b_root = find(b)
    if a_root != b_root:
        if a_root < b_root:
            parent[b_root] = a_root
        else:
            parent[a_root] = b_root

# 6. Kruskal 최소 신장 트리 구성
bridges.sort()
total_length = 0
connection_count = 0

for length, a, b in bridges:
    if find(a) != find(b):
        union(a, b)
        total_length += length
        connection_count += 1

# 7. 모든 섬이 연결되어 있는지 확인
roots = set(find(i) for i in range(2, island_id))
print(total_length if len(roots) == 1 else -1)

 

 

정답 제출을 하고 나서야 문제 유형을 보고 이게 Kruskal 알고리즘이었다는걸 알았고 MST도 새로 공부했다.

다리 만들기 1에 비해 확실히 고려할 조건이 많지만, MST와 유니온파인드의 연계 연습에 좋은 문제였던거같다~