문제 개요
n개의 도시가 있으며, 도시들은 고속도로(highway)와 지름길(shortcut)이라는 두 종류의 도로로 연결되어 있다고 가정해 보겠습니다. 현재 지도에는 고속도로만 표시되어 있고, 지름길은 표시되어 있지 않습니다. 교통 당국은 고속도로와 지름길을 모두 활용해 도시들을 연결하는 대중교통 노선을 개설하려고 합니다.
여기서 핵심 규칙은 다음과 같습니다. 두 도시 사이에 고속도로가 없다면, 그 사이에는 반드시 지름길이 존재합니다. 따라서 우리의 과제는 시작 도시에서 출발하여 나머지 모든 도시까지 도달하는 데 필요한 지름길 기반의 최소 거리를 계산하는 것입니다.
예제 살펴보기
입력이 아래와 같다고 가정해 봅시다.
시작 정점(s)이 1일 때, 출력은 3 1 2가 됩니다.
지름길만 사용할 경우 도시 1과 2 사이의 경로는 1→3→4→2이며, 비용은 3입니다. 마찬가지로 다른 도시들도 다음과 같이 계산됩니다.
- 1과 3: 1→3, 비용 1
- 1과 4: 1→3→4, 비용 2
풀이 접근 방법
이 문제는 너비 우선 탐색(BFS)과 유사한 집합(set) 기반 접근법으로 해결할 수 있습니다. 핵심 아이디어는, 현재 탐색 범위에 있는 도시 중 하나라도 고속도로로 직접 연결되어 있지 않다면 그 도시와는 지름길로 연결된다는 점입니다. 단계별 과정은 다음과 같습니다.
- graph := n개의 집합을 담는 새 리스트 생성
- edges의 각 쌍 (x, y)에 대해:
- x := x - 1, y := y - 1 (0 기반 인덱스로 변환)
- graph[x]에 y를, graph[y]에 x를 삽입 (양방향 연결)
- temp_arr := 크기 n이고 값이 모두 -1인 새 배열
- b_set := 시작 정점 s-1을 포함하는 새 집합
- f := 0부터 n-1까지의 숫자 집합에서 b_set을 뺀 차집합
- index := 0
- b_set이 빌 때까지 반복:
- b_set의 각 원소 a에 대해 temp_arr[a] := index 할당
- nxt := graph[f]가 b_set의 부분집합이 아닌 f들의 집합 (즉, b_set에 속한 어떤 도시와 고속도로로 직접 연결되지 않아 지름길이 존재하는 도시들)
- f := f에서 nxt를 뺀 차집합
- b_set := nxt
- index := index + 1
- temp_arr에서 0보다 큰 값들을 반환
구현 예제
아래 파이썬 구현을 통해 더 자세히 이해해 보겠습니다.
def solve(n, edges, s):
graph = [set() for i in range(n)]
for (x, y) in edges:
x -= 1
y -= 1
graph[x].add(y)
graph[y].add(x)
temp_arr = [-1] * n
b_set = {s - 1}
f = set(range(n)).difference(b_set)
index = 0
while len(b_set) > 0:
for a in b_set:
temp_arr[a] = index
nxt = {f for f in f if not b_set.issubset(graph[f])}
f = f.difference(nxt)
b_set = nxt
index += 1
return (' '.join(str(t) for t in temp_arr if t > 0))
print(solve(4, [(1, 2), (2, 3), (1, 4)], 1))입력
4, [(1, 2), (2, 3), (1, 4)], 1
출력
3 1 2
마무리
이 알고리즘은 일반적인 BFS가 '연결된 정점'을 따라 탐색하는 것과 달리, '연결되지 않은 정점', 즉 지름길이 존재하는 정점을 따라 탐색한다는 점이 특징입니다. 각 반복 단계마다 거리 값(index)이 하나씩 증가하므로, 결과적으로 시작 도시에서 각 도시까지 지름길을 몇 번 거쳐야 하는지가 배열에 저장됩니다. 고속도로 정보만 주어진 상황에서도 집합 연산을 활용하면 효율적으로 최단 거리를 계산할 수 있습니다.