아이디어
문제에서 구하고자 하는 것은 1번 노드로부터 가장 멀리 떨어진 노드의 개수이다.
가장 멀리 떨어진 것은 어떻게 판단할까?
문제에서 주어진 간선 정보로 판단할 수 있다.
즉, 특정 노드까지 이동할 때 거치는 간선이 가장 많은 것이 가장 멀리 떨어진 것이라고 볼 수 있다.
문제에서도 이와 같이 언급한다.
가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.
여기서 키 포인트는 최단경로이다.
그래프 상에서 최단 경로를 구할 때는 일반적으로 2개의 알고리즘을 사용할 수 있다.
- 다익스트라
- 플로이드-와샬
문제의 제한사항을 살펴보면, 노드의 개수는 최대 20,000개, 간선의 개수는 최대 50,000개 이다.
여기서 다익스트라를 사용해야겠다고 떠올렸다.(플로이드-와샬의 시간 복잡도는 이므로 시간초과 발생)
코드
# 그래프 상 최단 경로 구하기 & 특정 노드에서 다른 모든 노드까지 : 다익스트라(Dijkstra)
# 노드의 최대 개수 : 20,000개
# 간선의 최대 개수 : 50,000개
# 멀리 떨어진 것을 어떻게 판단? : 간선에 임의로 가중치를 설정하고, 거리를 찾는다.
from heapq import heappush, heappop
INF = int(1e9)
def solution(n, edge):
answer = 0
dist = [INF] * (n + 1) # 최단 거리 리스트
graph = [[] for _ in range(n + 1)] # 그래프 정보
# 양방향 그래프 초기화
# 가중치는 1로 설정
for a, b in edge:
graph[a].append((b, 1))
graph[b].append((a, 1))
# 개선된 다익스트라 알고리즘
def dijkstra(start):
q = []
heappush(q, (0, start)) # 비용: 0, 시작노드: 1번 노드
dist[start] = 0 # 시작노드의 최단 거리는 0
while q:
d, cur = heappop(q)
# 이미 최단 거리 설정이 되어있다면 무시
if dist[cur] < d:
continue
# 연결된 노드(nxt) 확인
# nxt[0] : 노드번호, nxt[1] : 가중치
for nxt in graph[cur]:
cost = d + nxt[1]
# 현재 노드(cur)를 거쳐서 다음 노드(nxt[0])로 이동하는 거리가 더 짧은 경우
if cost < dist[nxt[0]]:
dist[nxt[0]] = cost # 최단거리 갱신
heappush(q, (cost, nxt[0]))
dijkstra(1) # 1번노드를 시작점으로 설정하여, 다익스트라 수행
_max = max(dist[1:]) # 1-index이므로 1번 인덱스부터 최댓값 확인
answer = dist.count(_max) # 가장 멀리 떨어진 노드가 여러 개 일 수 있다.
return answer풀이
특이하게 살펴볼만한 코드는 없다. 일반적인 다익스트라 알고리즘을 구현하면 된다.
굳이 3가지로 흐름을 나눠보자면,
- 양방향 간선 정보를 토대로 그래프 정보 생성하기
- 개선된 다익스트라 알고리즘 수행
- 가장 먼 노드 찾기(다수의 노드일 수 있음)
양방향 간선 정보를 토대로 그래프 정보 생성하기
그래프 정보를 담을 2차원 리스트(graph)를 생성한다.
간선의 가중치는 1로 설정하고 주어진 edges 리스트로 그래프 정보를 초기화한다.
(단, 이때 간선은 양방향임에 주의하자.)
graph = [[] for _ in range(n + 1)] # 그래프 정보
# 양방향 그래프 초기화
# 가중치는 1로 설정
for a, b in edge:
graph[a].append((b, 1))
graph[b].append((a, 1))가장 먼 노드 찾기(다수의 노드일 수 있음)
다익스트라를 수행했다면, 최단 거리 리스트(dist)가 모두 완성된다.
초기에 dist 리스트를 1-index로 초기화했으므로, dist[1:]부터 최댓값을 찾아준다.
그리고, 가장 먼 노드가 여러개 일 수 있으므로 위에서 찾은 최댓값으로 count()를 사용하여 노드의 개수를 찾아준다.
_max = max(dist[1:]) # 1-index이므로 1번 인덱스부터 최댓값 확인
answer = dist.count(_max) # 가장 멀리 떨어진 노드가 여러 개 일 수 있다.다른 코드
deque + BFS사용
# 노드의 최대 개수 : 20,000개
# 간선의 최대 개수 : 50,000개
# 멀리 떨어진 것을 어떻게 판단? : 간선에 임의로 가중치를 설정하고, 거리를 찾는다.
from collections import deque
INF = int(1e9)
def solution(n, edge):
answer = 0
dist = [INF] * (n + 1) # 최단 거리 리스트
graph = [[] for _ in range(n + 1)]
# 그래프 정보 초기화
for a, b in edge:
graph[a].append(b)
graph[b].append(a)
# BFS
def bfs(start):
q = deque([start])
dist[start] = 0 # 시작노드의 최단 거리는 0
while q:
cur = q.popleft()
# 연결된 노드(nxt) 확인
for nxt in graph[cur]:
if dist[nxt] == INF:
dist[nxt] = dist[cur] + 1
q.append(nxt)
bfs(1) # 1번노드를 시작점으로 설정하여 BFS 수행
_max = max(dist[1:]) # 1-index이므로 1번 인덱스부터 최댓값 확인
answer = dist.count(_max) # 가장 멀리 떨어진 노드가 여러 개 일 수 있다.
return answer처음 작성한 코드보다 소요되는 시간이 짧다.
다익스트라를 사용하지 않고 BFS를 사용한다.
거리 갱신은, 해당 노드의 최단 거리 테이블의 값이 INF일 때만 갱신하는 방식이다.
즉, INF라면 처음 방문했다는 의미이므로 최단 거리를 갱신한다.
간선의 가중치가 1이므로, 처음 방문했을 때가 무조건 최단거리이다.
