프로그래머스 level 3- 가장 먼 노드

https://programmers.co.kr/learn/courses/30/lessons/49189

코딩테스트 연습 - 가장 먼 노드

 

#Idea

BFS의 가장 기본 개념을 묻는 문제이다. 시작 노드에서 level 별로 노드들을 탐색하고, 가장 깊이 있는 노드의 개수를 세면 된다. 이미 지난 정점만 visited list를 이용해 잘 체크해주면 아주 쉬운 문제이다. 

+) Queue를 사용하는 BFS 기본 개념은 아래 포스팅 참고

https://mslilsunshine.tistory.com/135

그래프와 관련 알고리즘(DFS,BFS)

 

#나의 풀이

def solution(n, edge):
    answer = 0

    route=[0 for i in range(n+1)]
    graph = [[] for i in range(n+1)] #각 노드에 연결된 노드 정보 저장
    
    for e in edge: # 양방향이므로 
        graph[e[0]].append(e[1])
        graph[e[1]].append(e[0])
        
        
    queue,visited=list(),list()
    queue.append(1)
    
    while queue:
        node=queue.pop(0)
        visited.append(node)
        for i in graph[node]:
            if route[i]==0 and i not in visited:
                queue.append(i)
                route[i] =route[node]+1
    
    maxlevel=max(route)
    for i in route:
        if i==maxlevel:
            answer+=1
            
    return answer

 

#개선사항

: 뭔가 실행시간이 겁나 오래걸렸다. 찾아보니 파이썬에 deque라는 라이브러리가 있으니 그것을 사용해보자.

-> list 사용시 시간 복잡도가 상당히 오래걸릴 여지가 있으니 이를 deque로 바꿔보자

 

 

2) 그리고 이미 route를 이용해서 visited와 같은 효과를 낼 수 있는데 node가 visited 배열에 존재하는지 찾아보는 not in 연산까지 하느라고 더 시간이 오래 걸린 듯 하다. 이는 route[1] 값을 처음부터 1로 설정함으로써 route[1]값은 이미 노드를 방문했는지 체크하는 route[i]==0 조건에 안 걸리도록 해보자. 

=> 문제는 위보단 이거 때문이었다.. 시간 훠어얼씬 개선됨. 그래도 알아두면 좋으니까~

 

#개선된 코드

from collections import deque

def solution(n, edge):
    answer = 0

    route=[0 for i in range(n+1)]
    graph = [[] for i in range(n+1)] #각 노드에 연결된 노드 정보 저장
    
    for e in edge: # 양방향이므로 
        graph[e[0]].append(e[1])
        graph[e[1]].append(e[0])
        
        
    queue=deque()
    queue.append(1)
    route[1]=1
    while queue:
        node=queue.popleft()
        
        for i in graph[node]:
            if route[i]==0:
                queue.append(i)
                route[i] =route[node]+1
    
    maxlevel=max(route)
    for i in route:
        if i==maxlevel:
            answer+=1
            
    return answer

끔찍한 시간....