[BOJ] 백준 1647 도시 분할 계획

Jihan·2024년 5월 16일

알고리즘

목록 보기

5/6

백준 Online Judge 문제

체크리스트

✅ 해결 🟩 미해결 🟩 포기
풀이에 걸린 시간:

풀이가 떠오른 과정

🟩 문제를 읽고 주어진 시간제한과 메모리제한 내에서의 풀이가 떠올랐다.
🟩 문제를 읽고 시간제한과 메모리제한 내에서 해결이 가능한 지는 모르겠지만 풀이가 떠올랐다.
✅ 문제를 읽고 풀이가 떠오르지 않았다.
🟩 문제가 곧바로 이해되지 않았다.

풀이 작성 과정

🟩 풀이를 아무런 도움 없이 작성하였다.
✅ 풀이를 관련된 알고리즘 지식만을 찾아 숙지한 채 작성하였다.
🟩 풀이를 남의 정답코드를 찾아 참고하여 작성하였다.
🟩 알고리즘 개념에 대한 공부를 하다 해당 개념에 대한 문제를 찾았고, 풀었다.

알고리즘 개념

최소 스패닝 트리(Minimum Spanning Tree, MST)

최소 스패닝 트리(최소 신장 트리)는 주어진 방향성이 없는 그래프의 부분 그래프들 중, 모든 정점을 포함하면서 간선의 가중치의 총합이 최소가 되도록 하는 트리를 뜻한다. 최소 스패닝 트리는 다음 조건들을 만족한다.

주어진 그래프의 서브 그래프(정점과 간선이 모두 포함)이다.
주어진 그래프의 모든 정점을 포함한다.
정점의 개수를 V라고 했을 때, V-1개의 간선을 포함한다.
2, 3번에 의해서 주어진 그래프의 모든 정점끼리 최소한의 간선으로 연결된다.
마찬가지로 2,3으로 인해 싸이클을 포함하지 않는다.
위의 내용들을 모두 만족하면 스패닝 트리이며, 간선의 가중치의 총합이 최소인 스패닝 트리를 최소 스패닝 트리라고 한다.

최소 스패닝 트리는 모든 정점을 지나면서 간선의 길이의 총합이 최소가 되도록 하는, 최소 비용 도출 문제 해결에 활용된다. 최소 비용 네트워크 구축 문제나, 도시의 도로 건설 비용 문제 등이 그 예시이다.

특정한 그래프가 주어졌을 때 최소 스패닝 트리를 구하는 방법은 크게 두 가지가 잘 알려져 있는데, 크루스칼 알고리즘과 프림 알고리즘이다. 이번 문제에서는 크루스칼 알고리즘을 활용하여 최소 스패닝 트리를 구하였다.

크루스칼 알고리즘(Kruskal Algorithm)

크루스칼 알고리즘은 다음과 같은 과정으로 그래프 내의 최소 스패닝 트리를 찾아낸다.

간선을 비용순으로 정렬한다.
비용이 낮은 간선부터 차례로 트리에 포함시킨다. 이 때 양쪽 정점이 이미 트리에 포함되어 있으면 그 간선은 배제한다.

1번에서 정렬로 인한 시간복잡도 O(ElogE)와 2번에서 양쪽 정점이 트리에 포함되어 있는지 확인하면서 트리에 포함시키는 데에서 BFS를 활용할 경우 시간복잡도 O(V+E)이 발생하며, 각 간선에서 반복하므로 O(VE + E^2)의 시간복잡도가 발생한다.
총 O(E(logE+V+E))의 시간복잡도가 발생하는데, E < V - 1이므로 대략 O(VE)라고 보아도 된다.
근데 2번에서 Union Find를 활용하여 양쪽 정점이 트리에 포함되어 있는지를 확인하게 된다면, O(V+E)가 아닌 O(k)의 시간복잡도가 발생하여, O(ElogE + Ek) = O(E(logE + k)) = O(ElogE)의 시간복잡도로 문제를 해결할 수 있게 된다.
따라서 최적화를 위해서는 아래의 Union Find를 활용하여 구현하는 것이 좋겠으며, 이번 문제 풀이에서는 Union Find를 활용하여 크루스칼 알고리즘을 구현하였다.

간선을 비용순으로 정리하여 비용이 작은 간선부터 채택한다는 것은, 가중치가 같은 간선이 여럿 존재할 때 두 번째 정렬 우선순위에 따라 도출되는 트리가 달라지게 될 수 있다는 것인데, 이는 최소 스패닝 트리가 유일하지 않다는 특징과 크루스칼 알고리즘이 지역해를 탐색하는 그리디 알고리즘의 일종이라는 특징을 잘 나타낸다.
크루스칼 알고리즘이 전역적 최적해를 도출하는 그리디 알고리즘이라는 점은 매트로이드 알고리즘을 활용하여 증명할 수 있다고 한다.

유니온 파인드(Union Find)

유니온 파인드는 여러 개의 노드가 존재할 때, 두 개의 노드를 선택하여 두 노드가 같은 그래프에 속하고 있는지를 판별할 수 있게 해주는 알고리즘이다. 유니온 파인드는 다음과 같은 방법으로 진행된다.

자기 자신을 부모 값으로 기억하고 있는, 정점의 개수와 길이가 같은 배열을 생성한다.
모든 간선 정보를 순회하면서, 각 간선이 가리키는 양쪽 노드 중에서 작은 노드를 부모 노드로 하여 연결해준다.(Union)
이 때, 예외 상황이 발생할 수 있게 된다.
예를 들어, 1과 2를 연결해주어 1:1, 2:1인 상태에서, 2와 3을 연결하게 된다면 1:1, 2:1, 3:2가 된다. 우리가 3에서 출발한다면 3과 1이 연결되어 있음을 확인할 수 있지만, 단순히 부모 노드의 값만으로 1과 3이 연결되어있다는 것은 확인할 수가 없다. 만약 모든 간선에 대한 순회가 끝난 후에 일괄적으로 모든 간선들에 대해 이러한 루트 노드 값을 추적하여 갱신해줄 수는 있지만, 이는 O(E * 트리높이)만큼의 시간복잡도를 발생시킨다.
Union의 초기화 과정에서 항상 최상위 부모값으로 이를 초기화해준다면, 1과 2가 연결된 상태(1:1, 2:1)에서 2와 3을 연결하게 되면 2의 부모인 1의 값으로 3의 부모를 초기화하게 되어 이를 해결할 수 있다.(1:1, 2:1, 3:1) (Find)
일반적으로 이는 재귀함수를 통해 구현하는데, 다음과 같은 형태로 구현하는 것이 일반적이다.

parents = [ i for i in range(N + 1) ]

 def getParent(num):
  if parents[num] != num:
    parent = getParent(parents[num])
    parents[num] = parent
    return parent
  return num

def getIsSameGroup(nodeA, nodeB):
  return getParent(nodeA) == getParent(nodeB)

def union(nodeA, nodeB):
  parentA, parentB = getParent(nodeA), getParent(nodeB)
  if parentA < parentB:
    parents[parentB] = parentA
  else:
    parents[parentA] = parentB

간선 정보를 순회하면서 각 간선이 가리키는 양쪽 노드 중에서 일반적으로 작은 노드를 부모 노드로 하여 연결해주는 것을 반복해주면, 각 노드들이 가리키는 루트노드의 값들을 알 수 있게 된다. 여기서 가리키고 있는 루트노드의 값이 같다면 같은 그래프에 속해있는 것으로 볼 수 있다.

풀이과정

크루스칼 알고리즘으로 최소 스패닝 트리 도출
주어진 도시에서의 최소 스패닝 트리는 모든 정점을 연결하는 최소한의 가중치 간선들의 모임이므로, 여기서 가장 가중치가 높은 간선을 제외하면 도시는 둘로 나눠지면서 각 도시의 가중치의 총합은 최소값으로 유지되게 된다.

코드

import sys;rl=sys.stdin.readline

N,M = map(int,rl().split())

vertexes = []
for _ in range(M):
  vertexes.append(list(map(int,rl().split())))
vertexes.sort(key=lambda x: x[2])

parents = [ i for i in range(N + 1) ]

def getParent(num):
  if parents[num] != num:
    parent = getParent(parents[num])
    parents[num] = parent
    return parent
  return num

def getIsSameGroup(nodeA, nodeB):
  return getParent(nodeA) == getParent(nodeB)

def union(nodeA, nodeB):
  parentA, parentB = getParent(nodeA), getParent(nodeB)
  if parentA < parentB:
    parents[parentB] = parentA
  else:
    parents[parentA] = parentB

maxCost = 0
sumCost = 0
cnt = 0
for start,end,cost in vertexes:
  if getIsSameGroup(start, end):
    continue
  union(start,end)
  sumCost += cost
  cnt += 1
  if maxCost < cost:
    maxCost = cost
  if cnt == N - 1:
    break

print(sumCost - maxCost)

이전에 알고리즘 공부를 할 때도, 선형대수학을 공부할 때도 분명 꼼꼼히 공부했던 그래프이론 중 최소 스패닝 트리 파트이다. 근데 역시나 까먹었다. 하하...
이번에 알고리즘 문제풀이를 진행하면서 사실 기억이 안 나거나 새롭게 보게 되어 처음부터 다시 공부하고 찾아봐야하는 알고리즘은 문제 풀이에 시간이 너무 오래 걸려서 조금 꺼렸는데, 그래도 다시 공부해보니 나름 재미도 있고 기억 났을 때 쾌감도 있는 것 같다.
이번 포스팅을 마지막으로 최소 스패닝 트리, 크루스칼 알고리즘, 유니온 파인드는 개념을 좀 잘 기억하게 되었으면 좋겠다...