[백준] 17472번 : 다리만들기 2

17472번: 다리 만들기 2

17472번: 다리 만들기 2

📄 문제개요

• 섬과 바다가 주어지고, 주어진 조건에따라서 섬을 연결 할 수 있다고 할 때, 섬을 연결 할 수 있는 최소 길이를 구하여라, 연결하지 못한다면 -1을 출력하여라.

🤔 문제분석

• 탐색과 그래프 문제입니다. BFS 탐색으로 섬을 그룹핑 한다.
• 해당 그룹에서 또다른 그룹 까지의 거리를 구한다.
• 해당그룹에서 또다른그룹까지의 거리를 가장 짧은 거리순으로 연결해본다 ( 최소신장트리 )

📝 의사코드

1. BFS 탐색으로 그룹을 구한다. 그래프도 업데이트한다. (1,2,3,4,…N) 으로 그룹핑을 한다.
2. 해당 그룹에서 또다른 그룹까지의 최소 거리를 구한다.
   1. BFS 탐색으로 구현하였고, 특정 방향만 이동하는 큐이다.
3. 간선의 정보를 모두 저장해둔다.
4. 간선의 정보를 거리순으로 정렬한다.
5. 유니온, 파인드로 최소신장 트리를 구한다.
6. 최소신장 트리를 만족하면 거리를 출력, 그렇지 않다면 -1을 출력한다.
   1. 최소신장 트리를 구하는 조건은 연결된 다리의 수와 그룹의 개수 -1 이 같아야한다.

💻 코드

import sys
from collections import deque

input = sys.stdin.readline

N, M = map(int, input().split())
graph = []
moves = [(0, 1), (0, -1), (1, 0), (-1, 0)]
for _ in range(N):
    graph.append(list(map(int, input().split())))
    
visited = [[False for _ in range(M)] for _ in range(N)]
group_name = 0
group = []

# 그룹이름으로 나누기
for i in range(N):
    for j in range(M):
        if graph[i][j] == 1 and not visited[i][j]:
            group_name += 1
            queue = deque()
            queue.append((i, j))
            visited[i][j] = True
            graph[i][j] = group_name
            group.append([(i, j)])
            while queue:
                y, x = queue.popleft()
                for dy, dx in moves:
                    ny, nx = dy + y, dx + x
                    if N > ny >=0 and M > nx >=0 and graph[ny][nx] == 1 and not visited[ny][nx]:
                        visited[ny][nx] = True
                        graph[ny][nx] = group_name
                        queue.append((ny, nx))
                        group[group_name-1].append((ny, nx))
                        

# 특정그룹에서 또다른 그룹까지의 간선정보 구하기
connect_info = []
for name, g in enumerate(group):
    visited = [[False for _ in range(M)] for _ in range(N)]
    queue = deque()
    for land in g:
        for dir in range(4):
            queue.append((land[0], land[1], 0, dir))
        visited[land[0]][land[1]] = True
    while queue:
        y, x, cost, d = queue.popleft()
        ny, nx = moves[d][0] + y, moves[d][1] + x
        
        if N > ny >=0 and M > nx >=0 and not visited[ny][nx]:
            visited[ny][nx] = True
            if graph[ny][nx] == 0:
                queue.append((ny, nx, cost + 1, d))
            else:
                if (name+1 , graph[ny][nx], cost) not in connect_info and cost != 1:
                    connect_info.append((name +1, graph[ny][nx], cost))
                    

parent = [i for i in range(len(group))]

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

def union(a, b):
    v1 = find(a)
    v2 = find(b)
    if v1 > v2:
        parent[v1] = v2
    else:
        parent[v2] = v1
        
connect_info.sort(key=lambda x:x[2])

ans = 0
con_cnt = 0
for v1, v2, cost in connect_info:
    p1, p2 = find(v1-1), find(v2-1)
    if p1 != p2:
        con_cnt += 1
        ans += cost
        union(v1-1, v2-1)
    

if con_cnt == len(group) -1:
    print(ans)
else:
    print(-1)

🎯 피드백 및 개선사항

• 어렵지 않은 문제로, 문제의 조건에따라서 구현만 잘 하면 되는 문제이다.

❓다른사람은 어떻게 풀었을까?

• 섬의 최소 길이를 구하는 방법으로, DFS탐색을 하여 구하였다.
• 나머지는 비슷하다