JinWoo Kim

백문이 불여일견, 백견이 불여일행.

3 minute read

1. 대운하

  • 4대강 사업의 성공에 힘입은 정부는 대한민국의 도시들을 모두 운하로 연결하여 뱃길로 KTX를 대체하려는 계획을 세웠다.

  • 대한민국에는 N개의 도시가 있고, 이들을 연결하는 M개의 운하를 건설하려고 한다.
    • 배의 폭이 운하의 폭보다 작거나 같아야 운하를 무사히 통과할 수 있기 때문이다.
  • 정부는 K개의 노선을 준비했다.
    • 각 노선의 도시 i와 j간을 운행하는 배는 도시 i와 j 간의 경로에 포함되는 운하를 통과할 수 있어야 한다.
      • (이 경로는 여러 개가 존재할 수 있다.)

  • 배가 클수록 많은 사람을 실을 수 있으므로, 정부는 배의 폭을 최대화하기를 원한다.

  • N개의 도시는 운하로 서로 연결되어 있음이 보장되며, 운하는 양방향으로 통행이 가능하다.

입력

  • 입력의 첫 번째 줄에는 도시의 수 N, 운하의 수 M, 노선의 수 K가 주어진다. (N ≤ 1000, M ≤ 100000, K ≤ 10000)

  • 다음 M개의 줄에는 세 정수 i, j, w가 주어지며, 이는 도시 i와 j 사이에 폭이 w인 운하를 건설할 것임을 의미한다. (1 ≤ i, j ≤ N, w ≤ 200)

  • 다음 K개의 줄에는 각 노선이 연결하는 도시 i, j가 주어진다. (1 ≤ i, j ≤N)

출력

  • K개의 줄에 각 노선을 운행할 수 있는 최대 배의 폭을 출력한다.

풀이

# your code goes here
 
import sys
 
# 입력의 첫 번째 줄에는 도시의 수 N, 운하의 수 M, 노선의 수 K가 주어진다. (N ≤ 1000, M ≤ 100000, K ≤ 10000)
 
N, M, K = list(map(int,sys.stdin.readline().split()))
 
# 다음 M개의 줄에는 세 정수 i, j, w가 주어지며,
# 이는 도시 i와 j 사이에 폭이 w인 운하를 건설할 것임을 의미한다. (1 ≤ i, j ≤ N, w ≤ 200)
# 점i와 점j를 w의 폭으로 잇는다.
# 운하는 양방향으로 통행이 가능하다.
 
graph = {}
 
for _ in range(0,M):
	i,j,w = list(map(int,sys.stdin.readline().split()))
 
 
	# [정점에 연결된 점,폭]으로 그래프를 구성
	if i not in graph.keys():
		graph[i] = [[j,w]]
	else:
		graph[i].append([j,w])
 
	# 양방향 연결이므로, 반대쪽도 똑같이 그래프를 구성
	if j not in graph.keys():
		graph[j] = [[i,w]]
	else:
		graph[j].append([i,w])
 
 
def dfs(start,end,visited,w):
	visited.append(start)
	for point in graph[start]:
		if point[0] == end:
			return point[1] if point[1] < w else w
		elif point[0] in visited:
			continue
		elif point[0] not in visited:
			w2 = dfs(point[0],end,visited,point[1])
			w = w2 if w2 < w else w
 
	return w
 
 
 
 
# 다음 K개의 줄에는 각 노선이 연결하는 도시 i, j가 주어진다. (1 ≤ i, j ≤N)
for _ in range(0,K):
	start,end = list(map(int,sys.stdin.readline().split()))
	print(dfs(start,end,[],201))

채점 결과

  • 오답

리뷰

  • 처음에는 최대한 알고 있던 지식인 dfs나 그래프를 활용해 풀어보려 했으나, 쉽게 답이 나오지 않았다.

  • 이에 어떤 알고리즘이 사용되었는지 확인했고, MST이라는 개념이 사용되었음을 확인했다.

  • 개념 정리 후에 다시 풀어보기로 했다.

개념 정리

Spanning Tree(신장 트리)

  • 그래프 내의 모든 정점을 포함하는 트리

  • 그래프의 최소 연결 부분 그래프 이다.
    • 최소 연결 = 간선의 수가 가장 적다
    • n개의 정점을 가지는 그래프의 최소 간선의 수는 n-1개이다.
    • n-1개의 간선으로 연결된 그래프는 트리 형태이므로, 이것이 신장 트리가 된다.
  • 즉, 그래프에서 일부 간선을 선택해서 만든 트리이다.

Spanning Tree의 특징

  • DFS, BFS를 이용하여 그래프에서 신장 트리를 찾을수 있다.
    • 탐색 도중에 사용된 간선만 모으면 만들수 있다.

  • 하나의 그래프에는 많은 신장 트리가 존재할 수 있다.

  • Spanning Tree는 트리의 특수한 형태이므로 모든 정점들이 연결되어있어야 하고, 사이클을 포함해서는 안된다.

  • 따라서 Spanning Tree는 그래프에 있는 n개의 정점을 정확히 n-1개의 간선으로 연결한다.

MST(Minimum Spanning Tree)

  • 간선의 가중치를 고려하여 최소 비용의 Spanning Tree를 선택하는것을 말한다.

MST의 특징

  • 간선의 가중치 합이 최소여야 한다.
  • n개의 정점에 대해 반드시 n-1개의 간선만을 사용해야 한다.
  • 사이클이 포함되어서는 안된다.

MST 구현 방법

  1. Kruskal MST 알고리즘

    • 탐욕법을 이용하여 네트워크의 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는 것

    • 이전 단계에서 만들어진 신장 트리와는 상관없이 무조건 최소 간선만을 선택하는 방법이다.

    • 과정

      1. 그래프의 간선들을 가중치의 오름차순으로 정렬한다.
      2. 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택한다.
      3. 해당 간선을 현재의 MST의 집합에 추가한다.
  2. Prim MST 알고리즘

    • 시작 정점에서 출발하여 신장트리 집합을 단계적으로 확장해나가는 방법

    • 과정

      1. 시작 단계에서는 시작정점만 MST집합에 포함한다.
      2. 앞 단계에서 만들어진 MST집합에 인접한 정점들중 최소 간선으로 연결된 정점을 선택하여 트리를 확장한다.
        • 즉, 가장 낮은 가중치를 먼저 선택한다.
      3. 위의 과정을 트리가 N-1개의 간선을 가질때까지 반복한다.

풀이

채점 결과

  • 오답

You May Also Enjoy