2학년 2학기 알고리즘 과제_3주차(백준_1045번:도로)

 

1045번: 도로

 

문제

0부터 N-1까지의 번호가 매겨져 있는 N개의 도시와 두 도시를 연결하는 도로가 있다. 도로에는 우선순위가 있는데, A와 B가 (A < B) 도로 x로 연결되어 있고, C와 D가 (C < D) 도로 y로 연결되어 있을 때, 튜플 (A, B) < (C, D)이면 x > y, 즉 x의 우선순위가 더 높다. 여기서 ai ≠ bi인 가장 작은 양의 정수 i에 대해 ai < bi이면 (a1, ..., ak) < (b1, ..., bk)로 정의한다.

도로의 집합은 하나 이상의 도로가 우선순위에 대한 내림차순으로 정렬되어 있는 것이다. 집합 사이에도 우선순위가 있는데, 두 집합을 튜플로 나타냈을 때의 우선순위를 따른다. 한 집합에 있는 도로만으로 임의의 도시에서 임의의 도시로 이동할 수 있을 때, 그 집합은 연결되어 있다고 한다.

김지민이 할 일은 M개의 도로를 가진 도로의 집합 중 연결되어 있으면서 우선 순위가 가장 높은 것을 찾는 것이다.

입력

첫째 줄에 도시의 개수 N과 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N-1보다 크거나 같고, 1,000보다 작거나 같은 정수이다. 둘째 줄부터 N개의 줄에는 인접행렬이 주어진다. 즉 i번째 행의 j번째 열이 Y이면 도시 i와 j를 연결하는 도로가 존재하고, N이면 존재하지 않는다. i와 j가 연결되어 있으면 j와 i도 연결되어 있음이 보장되고, i와 i는 연결되어 있지 않다.

출력

만약 정답이 없을 때는 -1을 출력한다. 정답이 존재하면, 그 집합에 속하는 도로 중 0을 끝점으로 갖는 도로의 개수, 1을 끝점으로 갖는 도로의 개수, ..., N-1을 끝점으로 갖는 도로의 개수를 차례로 출력한다.

 

 

 

 

📌 내 풀이

 

 

• 우선 모든 도시가 연결되어있어야한다.
• 도시를 잇는 간선은 M개여야한다.
• i < j 인 간선들 중에서 i가 작은 순으로 나열하는데, i 가 같다면, j가 작은 순으로 나열한다.
• 이 때 모든 도시가 연결되있지 않으면 -1
• 간선의 수가 M개가 되지 못하면 -1
• 그리고, 상위 M개의 간선에서 시작점과 끝점의 index 카운팅해서 출력한다. 

 

 

이 뒤에 부분은 어떤 식으로 접근해야할지 고민이 됐다.

문제를 풀기위한 아이디어는 조금씩 모을 수 있었는데, 해당 문제를 풀기위해 알고리즘을 짜기는 어려워 찾아보았다.

 

 

• edge가 (a, b)가 있다면, a < b가 되도록 모든 간선을 우선순위 큐에 넣음
  • 이때 모든 간선의 개수가 m보다 작다면 -1을 출력한다.
• 크루스칼 알고리즘을 사용하여 mst를 만들기.
  • 만약 mst가 만들어지지 않으면, 모두 연결되지 않는 것이므로 -1을 출력
• 크루스칼 알고리즘을 진행하는 도중에 쓸모없는 간선은 따로 관리한다.
  • 이때 우선순위 큐로 집어 넣고, 해당 간선들은 추후 m개의 개수를 맞추기 위해 사용될 예정임
• 최종적으로 mst의 리스트와 쓸모 없는 간선의 리스트를 넣어서 m개의 리스트를 만듦
• 해당 리스트에 있는 노드를 answer 리스트에 더함

 

 

📌 코드 분석

 

import sys
import heapq
input = sys.stdin.readline


def my_par(x):
    while x != par[x]:
        x = par[x]
    return x


def union(x, y):
    par_x = my_par(x)
    while y != par[y]:
        temp, y = y, par[y]
        par[temp] = par_x
    par[y] = par_x


if __name__ == "__main__":
    n, m = map(int, input().split())
    maps = [list(input().strip()) for _ in range(n)]

    pq = []
    for i in range(n):
        for j in range(i, n):
            if maps[i][j] == 'Y':
                heapq.heappush(pq, (i, j))      # start < end가 될 수 있도록 엣지를 파악함

    if len(pq) < m:     # 엣지의 개수가 m이하라면 답이 없는 것
        print(-1)
        exit(0)

    trash = list()      # 우선 mst를 만들고, 뒤에 남는 애들을 넣어야 함
    par = [*range(n)]
    answer = [0] * n

    cnt = 0
    while pq:
        i, j = heapq.heappop(pq)
        if my_par(i) != my_par(j):
            union(i, j)
            answer[i] += 1      # 바로 정답에 더함
            answer[j] += 1
            cnt += 1
        else:
            heapq.heappush(trash, (i, j))       # 남는 쓰레기들을 넣어야 함

    if cnt != n - 1:        # 만약 mst가 만들어지지 않았으면 답이 없는 것임
        print(-1)
        exit(0)

    for _ in range(m - cnt):
        i, j = heapq.heappop(trash)
        answer[i] += 1
        answer[j] += 1

    print(*answer, sep=' ')

 

 

해당 코드는 주어진 그래프에서 최소 신장 트리(MST)를 구성하되, 특정 조건(m 개의 간선 사용)을 충족하도록 우선순위 큐(최소 힙)와 유니온-파인드(분리 집합) 구조를 이용하여 수정한 MST 알고리즘을 구현한 것이다.

 

 

my_par(x)

 

• x 노드의 최상위 부모를 찾는 함수로, while 루프를 통해 x의 부모가 자기 자신이 아닐 때까지 반복하면서 x의 최상위 부모를 반환하도록 한다.

이는 유니온-파인드에서 경로 압축을 적용해 집합의 대표를 찾는 방식 중 하나이다.

 

union(x, y):

• x와 y가 다른 집합에 있다면 이 둘을 하나의 집합으로 합치는 함수이다.
• my_par(x)와 my_par(y)를 사용해 x와 y의 최상위 부모를 찾고, y의 부모를 x의 최상위 부모로 설정하여 두 집합을 결합한다.

 

n, m = map(int, input().split())
maps = [list(input().strip()) for _ in range(n)]

 

 

• n은 노드의 개수, m은 필요한 간선의 개수를 나타낸다.
• maps는 인접 행렬 형태로 주어진 그래프의 정보를 저장하고,  'Y'로 표시된 위치가 간선이 존재하는 곳을 나타낸다.

 

간선 우선순위 큐 초기화하기

 

pq = []
for i in range(n):
    for j in range(i, n):
        if maps[i][j] == 'Y':
            heapq.heappush(pq, (i, j))

 

• Y로 표시된 간선들을 (i, j) 형태로 pq에 추가한다.
• 이것은 힙에 간선을 추가하여 우선순위 큐로 관리하려는 것이다.

 

if len(pq) < m:
    print(-1)
    exit(0)

 

• 주어진 간선의 개수가 m보다 적으면 원하는 조건을 만족시킬 수 없으므로 -1을 출력하고 프로그램을 종료한다.

 

trash = []
par = [*range(n)]
answer = [0] * n
cnt = 0

 

• trash는 MST를 구성하는 데 사용되지 않는 간선을 저장한다.
• par는 각 노드의 부모를 저장하며, 초기에는 자기 자신을 가리킨다.
• answer는 각 노드가 연결된 간선의 수를 저장한다.
• cnt는 MST를 이루는 간선의 개수를 셈.

while pq:
    i, j = heapq.heappop(pq)
    if my_par(i) != my_par(j):
        union(i, j)
        answer[i] += 1
        answer[j] += 1
        cnt += 1
    else:
        heapq.heappush(trash, (i, j))

 

• pq에서 간선을 하나씩 꺼내고, 그 간선이 서로 다른 집합에 속하는 경우 union을 통해 MST에 포함한다.
• 같은 집합에 속한다면 trash 리스트에 저장한다.

 

if cnt != n - 1:
    print(-1)
    exit(0)

for _ in range(m - cnt):
    i, j = heapq.heappop(trash)
    answer[i] += 1
    answer[j] += 1

 

• MST를 구성하는 데 필요한 간선 수가 부족하면 -1을 출력하고 종료한다.
• 남는 간선을 m에 맞출 때까지 trash에서 하나씩 가져와 answer에 반영함

 

print(*answer, sep=' ')

 

• 각 노드가 연결된 간선의 개수를 출력한다.

 

 

[알고리즘] 최소 신장 트리(MST, Minimum Spanning Tree)란 - Heee's Development Blog

 

 

 

Spanning Tree란
그래프 내의 모든 정점을 포함하는 트리이다.

Spanning Tree = 신장 트리 = 스패닝 트리
Spanning Tree는 그래프의 최소 연결 부분 그래프 이다.
최소 연결 = 간선의 수가 가장 적다.

n개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1)개이고, (n-1)개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 되고 이것이 바로 Spanning Tree가 된다.

즉, 그래프에서 일부 간선을 선택해서 만든 트리를 의미한다.

 

 

📌 느낀점

 

최소 신장 트리를 자료구조 시간에 배웠던 것 같은데, 막상 문제에 적용하려니, 헷갈리기도하고 다까먹은 것 같았다.

확실히 자료구조 시간에 배웠던 내용들이 알고리즘을 푸는데 많이 도움이 되고 있으니 관련된 내용을 복습해봐야겠다.

 

 

[참고 자료]

 

[백준 - Python] 1045 - 도로

[백준 - Python] 1045 - 도로