문제 설명
n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.
노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.
제한사항
- 노드의 개수 n은 2 이상 20,000 이하입니다.
- 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.
- vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.
입출력 예
| n | vertex | return |
|---|---|---|
| 6 | [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] | 3 |
입출력 예 설명
예제의 그래프를 표현하면 아래 그림과 같고, 1번 노드에서 가장 멀리 떨어진 노드는 4,5,6번 노드입니다.
풀이
각 정점까지의 최소 거리인 리스트 dists를 만들어 준다.
dists[i] : 정점 i까지의 최소 거리이때 dists[i]는 더 짧은 거리가 발견될 때마다 갱신해줄 것이기 때문에 처음에는 무한으로 설정한다.
그 다음은 흔한 bfs이다. queue에는 (vertex, 그 vertex까지의 거리)를 넣어준다. 처음에는 (1, 0)을 넣어주면 된다.
그리고 그 vertex의 이웃(adjacent)을 돌면서, 기존 이웃의 거리보다 해당 vertex를 거쳐서 가는 거리가 짧으면 갱신해 준다.
이때 중요한 것은 visited의 갱신이다.
queue에서 pop을 해 주고 난 다음에 visited를 True로 설정하면 시간 초과가 난다. queue에 넣기 전에 visited를 True로 설정해 주면, 불필요한 push를 막을 수 있다.
예를들어, adjacent를 queue에 넣을 때 [3, 4]가 들어갔다고 해 보자. 이때 3과 4도 서로 연결 돼 있다고 해보자. 3이 pop 된 순간에, 또 3의 adjacent를 돈다. 이때 4도 역시 3에 연결 돼 있다. 다만 visited가 True로 설정 돼 있지 않기 때문에, 다시 queue에 들어간다. 즉 4가 두 번 들어가는 것이다. 이런 불필요한 연산을 막기 위해, queue에 넣기 전에 visited를 True로 설정해 줘야 한다.
코드
from collections import defaultdict, deque
def makeGraph(n, edges) :
graph = defaultdict(list)
dists = defaultdict(int)
for v1, v2 in edges:
graph[v1].append(v2)
graph[v2].append(v1)
dists[v1] = float("inf")
dists[v2] = float("inf")
visited = [False] * (n+1)
return graph, visited, dists
def solution(n, edge):
answer = 0
graph, visited, dists = makeGraph(n, edge)
queue = deque()
queue.append((1, 0))
dists[1]= 0
visited[1] = True
while queue :
front, dist = queue.popleft()
for adjacent in graph[front] :
if visited[adjacent] == False :
visited[adjacent] = True
dists[adjacent] = min(dists[adjacent], dist + 1)
queue.append((adjacent, dists[adjacent]))
maxNum = max(dists.values())
for value in dists.values() :
if value == maxNum :
answer += 1
return answerdists를 dictionary로 설정한 이유는 vertex가 연속되지 않고 중간에 빠지는 경우(V = {1, 3, 5, 7, 9})와 같은 경우가 있을 거라 생각해서다.
의문이 가는 점, 개선해야할 점이 있다면 댓글로 알려주세요.
감사합니다☺️
