문제
n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.
노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.
제한 사항
•
노드의 개수 n은 2 이상 20,000 이하입니다.
•
간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.
•
vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.
예시
예제의 그래프를 표현하면 아래 그림과 같고, 1번 노드에서 가장 멀리 떨어진 노드는 4,5,6번 노드입니다.
정답
from collections import deque
def solution(n, edge):
network = dict() # network 만들기
for node in edge:
if node[0] not in network:
network[node[0]] = [node[1]]
else:
network[node[0]].append(node[1])
if node[1] not in network:
network[node[1]] = [node[0]]
else:
network[node[1]].append(node[0])
N = len(network)
distance = [-1]*(N+1) # node 1과의 거리
distance[1] = 0 # 스스로와의 거리는 0
q = deque(network[1]) # 1과 직접 연결되어있는 노드들
dist = 1
while q: # 거리를 재지 않은 노드가 없을 때까지
for _ in range(len(q)): # 새로 추가되는 노드 말고 현재 노드들만을 고려
n = q.popleft() # 하나씩 뽑으면서 살펴보기
if distance[n] == -1: # 거리가 정해지지 않은 경우
distance[n] = dist
for w in network[n]: # 연결된 노드 중에서 거리를 재지 않은 노드의 경우 추가
if distance[w] == -1:
q.append(w)
dist += 1
max_d = max(distance) # 최댓값
return distance.count(max_d) # 최댓값 개수
Python
복사
풀이
•
우선 dictionary를 통해서 network를 만들자.
•
이때 key는 노드이고 value는 연결된 노드의 리스트이다.
network = dict() # network 만들기
for node in edge:
if node[0] not in network:
network[node[0]] = [node[1]]
else:
network[node[0]].append(node[1])
if node[1] not in network:
network[node[1]] = [node[0]]
else:
network[node[1]].append(node[0])
Python
복사
•
다음은 1과의 거리를 나타내는 리스트를 만든다. 이 때 인덱스는 각 노드들을 의미한다. 예를 들어 distance[2] 는 1과 2 사이의 거리를 의미한다.
•
따라서 distance의 길이는 총 노드의 갯수(N) + 1 이어야 한다.
•
그리고 처음에 distance[1]은 자신과의 거리이므로 0을 설정하고 나머지는 -1로 설정한다.
N = len(network)
distance = [-1]*(N+1) # node 1과의 거리
distance[1] = 0 # 스스로와의 거리는 0
Python
복사
•
다음으로 덱을 생성한다. 이 때 덱은 1과의 거리를 잴 노드들을 모아놓은 것이다. 따라서 우선은 1과 직접적으로 연결되어있는 노드들을 덱에 포함시킨다.
q = deque(network[1]) # 1과 직접 연결되어있는 노드들
Python
복사
•
그 다음 q에 원소가 남지 않을 때 까지 반복하면서 다음을 수행한다.
•
현재 q에 들어있는 노드들은 1과 직접적으로 연결되어있는 값들이기 때문에 거리가 1이다. 따라서 현재 q에 들어있는 노드의 갯수만큼 leftpop을 통해서 뽑아내고 distance를 측정해주면 1과 직접적으로 연결되어 있는 노드들은 distance를 반영해줄 수 있다.
for _ in range(len(q)): # 새로 추가되는 노드 말고 현재 노드들만을 고려
Python
복사
•
for n in q 말고 range(len(q))를 사용한 이유는 q가 계속해서 변할 것이기 때문이다. 그리고 우리는 나중에 추가되는 노드들 말고 현재 저장되어 있는 노드들만을 고려하고 싶기 때문에 range(len(p))를 사용해서 현재 저장되어 있는 노드 수 만큼만 반복한다.
•
우선 q의 가장 앞에 있는 원소를 leftpop을 통해 뽑아낸다. 그 다음 그 원소가 1과의 거리가 아직 정해지지 않은 원소라면 현재 dist값을 distance 값으로 저장해준다.
n = q.popleft() # 하나씩 뽑으면서 살펴보기
if distance[n] == -1: # 거리가 정해지지 않은 경우
distance[n] = dist
Python
복사
→ 만약 이미 거리가 정해져 있으면 넘어간다.
•
그러고 나서 n과 연결되어 있는 노드들 중에서 아직 1과 거리가 정해지지 않은 노드들을 q에 포함시킨다.
for w in network[n]: # 연결된 노드 중에서 거리를 재지 않은 노드의 경우 추가
if distance[w] == -1:
q.append(w)
Python
복사
•
처음 저장되어 있던 p의 갯수만큼 for문을 수행했다면 이제 q에 남은 것은 1과 직접적으로 연결되어있는 값들이 아니라 1과 직접적으로 연결되어있는 노드들에 직접적으로 연결되어 있는 값일 것이다.
•
예를 들어 예시에서는 4,5,6이 될 것이다.
•
따라서 우리는 dist 값을 하나 올려주어야 한다.
dist += 1
Python
복사
•
그리고 q에 456이 남아있으므로 다시 for문을 통해 반복한다.
→ 그러면 4 5 6도 distance가 반영될 것.
•
1과 직접적으로 연결되어있는 노드들의 거리를 반영하는 순서를 정리하면 다음과 같다.
•
마지막으로 distance 값들 중 max 값을 찾아서 count를 해주면 된다.
max_d = max(distance) # 최댓값
return distance.count(max_d) # 최댓값 개수
Python
복사