문제 정의
n개의 도시와 이들을 연결할 수 있는 m개의 도로가 있다고 가정해 봅시다. 시민들이 생활 필수품을 구매하려면 시장이 반드시 필요하지만, 현재 어떤 도시에도 시장이 없고 도시 간 도로 역시 아직 건설되지 않은 상태입니다.
두 도시 사이에 양방향 도로를 새로 건설할 수 있는 조건은 다음과 같습니다.
- 두 도시 중 한 곳에 시장이 존재할 것
- 시장이 있는 도시에 기존 도로를 통해 도달할 수 있을 것
도로 한 개를 짓는 비용은 x, 시장 한 개를 짓는 비용은 y로 주어집니다. 목표는 모든 도시의 시민이 시장에 접근할 수 있도록 하는 최소 비용을 구하는 것이며, 배열 cities에는 도로로 연결 가능한 도시 쌍의 정보가 담겨 있습니다.
입출력 예시
예를 들어 입력이 n = 4, m = 3, x = 1, y = 2, cities = [[1, 2], [2, 3], [3, 4]]라면 출력은 4입니다.
위 그림처럼 도시 1, 2, 3, 4가 있을 때, 도시 1에 시장을 하나 짓고 (1, 4) 구간과 (1, 3) 구간에 도로 두 개를 추가로 건설하면 총비용은 2 + 1 + 1 = 4가 됩니다. 이것이 가능한 최소 비용입니다.
해결 전략
이 문제의 핵심은 비용 x와 y의 크기 관계에 따라 전략을 달리하는 것입니다.
- x ≤ y인 경우: 도로 건설 비용이 시장 건설 비용보다 크거나 같습니다. 따라서 도로를 잇는 대신 모든 도시에 각각 시장을 짓는 것이 가장 저렴하며, 총비용은 n × x입니다.
- x > y인 경우: 도로가 시장보다 저렴하므로, 서로 연결 가능한 도시 묶음(연결 요소)마다 시장을 단 하나만 짓고 나머지 도시는 모두 도로로 연결하는 것이 유리합니다. 각 연결 요소의 비용은 “시장 1개(x) + (요소에 속한 도시 수 − 1) × y”로 계산됩니다.
연결 요소를 효율적으로 찾기 위해 너비 우선 탐색(BFS)을 사용합니다. 아직 방문하지 않은 도시를 발견하면 그 도시에 시장 비용 x를 부여하고, BFS로 인접 도시를 차례로 방문하며 도로 비용 y를 누적하면 됩니다.
알고리즘 단계
- x ≤ y이면 n × x를 반환하고 종료합니다.
- 그렇지 않은 경우 다음을 수행합니다.
- cities 정보를 바탕으로 인접 리스트(adj_list)를 생성합니다.
- 크기 (n + 1)의 방문 여부 리스트 temp를 True로 초기화합니다.
- 누적 비용 value = 0, 빈 덱(deque)을 준비합니다.
- 1번부터 n번 도시까지 순회하며 아직 방문하지 않은 도시 cur을 만나면:
- value에 시장 비용 x를 더하고, cur을 덱에 넣은 뒤 방문 처리(temp[cur] = False)합니다.
- 덱이 빌 때까지 BFS를 반복하며, 인접한 미방문 도시 i를 덱에 추가하고 방문 처리한 후 value에 도로 비용 y를 더합니다.
- 모든 순회가 끝나면 value를 반환합니다.
인접 리스트 생성에 O(m), BFS에서 각 도시와 도로를 한 번씩만 확인하므로 전체 시간 복잡도는 O(n + m)으로 매우 효율적입니다.
파이썬 구현 예제
아래 코드를 통해 위 알고리즘이 실제로 어떻게 동작하는지 확인할 수 있습니다.
from collections import defaultdict, deque
def solve(n, m, x, y, cities):
if x <= y:
# 도로가 시장보다 저렴하지 않으면 모든 도시에 시장 건설
return n * x
else:
adj_list = defaultdict(list)
for city in cities:
city1 = city[0]
city2 = city[1]
adj_list[city1].append(city2)
adj_list[city2].append(city1)
temp = [True] * (n + 1)
value = 0
dq = deque()
for cur in range(1, n + 1):
if temp[cur]:
# 새로운 연결 요소 발견: 시장 1개 건설
value += x
dq.append(cur)
temp[cur] = False
# BFS로 같은 연결 요소의 나머지 도시를 도로로 연결
while dq:
for i in adj_list[dq.popleft()]:
if temp[i]:
dq.append(i)
temp[i] = False
value += y
return value
print(solve(4, 3, 1, 2, [[1, 2], [2, 3], [3, 4]]))
입력
4, 3, 1, 2, [[1, 2], [2, 3], [3, 4]]
출력
4
이 프로그램은 x ≤ y일 때는 모든 도시에 시장을 짓는 단순한 해답을, x > y일 때는 연결 요소별로 시장 하나와 최소한의 도로를 배치하는 해답을 자동으로 선택하여 항상 최소 비용을 보장합니다.