문제
- 문제 : 가장 먼 노드
코딩테스트 스터디에서 함께 풀었다가 시간초과를 얻었던 문제! 드디어 풀었다. 지난 번 풀이에서 시간초과를 받았던 이유는 다음과 같다.
-
2부터 n까지 모든 노드를 dest로 BFS를 n-1번 돌았다.
- 이에 따라 매번 count를 받아서, MAX값을 얻어 그 수를 세어주었다.
- dictionary로 graph를 받는게 아니라, 2차원 인접행렬로 만들어주면서 최대 20,000개를 모두 체크해주었다.
생각해보면 그냥 1을 시작으로, 모든 노드를 순회하기만 하면 되므로 BFS는 단 한 번만 돌면 된다.
또한, C++이나 자바라면 2차원 인접행렬로 돌아도 큰 문제가 없을 것 같은데, 느린 파이썬의 특징때문인지 딕셔너리로 도는 편이 더 빠른 것 같다. 파이썬은 메모리를 많이 사용하는 한이 있더라도, 무조건 적은 작업을 하는 편이 이득인 것 같다. (근거없음)
괜히 다들 딕셔너리로 풀었던 게 아닌 것 같다.
풀이
from collections import deque
def BFS(start, visited, graph) :
queue = deque([[start,0]])
visited[start] = True
cnt = 0
cntArr = [0]*len(visited)
while queue :
(node, cnt) = queue.popleft()
cntArr[node] = cnt
if node in graph :
for nextNode in graph[node] :
if not visited[nextNode] :
visited[nextNode] = True
queue.append([nextNode, cnt+1])
return cntArr
def solution(n, edges):
answer = 0
graph = {}
for edge in edges :
n1, n2 = edge[0], edge[1]
if n1 in graph :
graph[n1].append(n2)
else :
graph[n1] = [n2]
if n2 in graph :
graph[n2].append(n1)
else :
graph[n2] = [n1]
visited = [False]*(n+1)
cntArr = BFS(1, visited, graph)
return cntArr.count(max(cntArr))