[프로그래머스/Python] Level 3_가장 먼 노드

📌문제 유형

그래프, BFS

 

📌문제

프로그래머스

 

📌나의 문제풀이

[1차] 정확성 77.8, 이외 시간초과

from collections import deque

def solution(n, edge):
    answer = 0
    result = []
    
    # 간선 저장
    maps = [[] for _ in range(n+1)]
    for a,b in edge:
        maps[a].append(b)
        maps[b].append(a)
    
    # BFS 최소 간선의 개수
    q = deque([1])
    visited = [1]
    cnts = [0 for _ in range(n+1)]
    cnt = 0
    
    while q:
        node = q.popleft()
        cnt += 1
        
        for x in maps[node]:
            if x not in visited:
                q.append(x)
                visited.append(x)
                cnts[x] = min(cnts[node] + 1, cnt)  # 이미 거처온 노드 +1, 현재 cnt 
                # print(q, node,x, cnts, visited)

    # print(cnts)
    return cnts.count(max(cnts))

 

[2차] 정답 100

- visited.append -> visited[x] = 1로 변경

• if문 x not in visited(O(N)의 시간 복잡도) -> if문 visited[x] == 0(O(N)의 시간 복잡도)
• 미리 visited를 할당 or 추가로 시간 복잡도가 달라진 것 같음

from collections import deque
def solution(n, edge):
    answer = 0
    result = []
    
    # 간선 저장
    maps = [[] for _ in range(n+1)]
    for a,b in edge:
        maps[a].append(b)
        maps[b].append(a)
    
    # BFS 최소 간선의 개수
    q = deque([1])
    visited = [0 for _ in range(n+1)]
    visited[1] = 1
    cnts = [0 for _ in range(n+1)]
    cnt = 0
    
    while q:
        node = q.popleft()
        cnt += 1
        
        for x in maps[node]:
            if visited[x] == 0:
                q.append(x)
                visited[x] = 1
                cnts[x] = min(cnts[node] + 1, cnt)  # 이미 거처온 노드 +1, 현재 cnt 
                # print(q, node,x, cnts, visited)

    # print(cnts)
    return cnts.count(max(cnts))

 

 

📌다른사람의 문제풀이

- 다익스트라 이용

def solution(n, edge):
    graph =[  [] for _ in range(n + 1) ]
    distances = [ 0 for _ in range(n) ]
    is_visit = [False for _ in range(n)]
    queue = [0]
    is_visit[0] = True
    for (a, b) in edge:
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)

    while queue:
        i = queue.pop(0)

        for j in graph[i]:
            if is_visit[j] == False:
                is_visit[j] = True
                queue.append(j)
                distances[j] = distances[i] + 1

    distances.sort(reverse=True)
    answer = distances.count(distances[0])

    return answer

 

 

📌리뷰

- 파이썬 자료형별 시간복잡도

파이썬 자료형 별 주요 연산자의 시간 복잡도 (Big-O) · 초보몽키의 개발공부로그

- 다익스트라 : BFS의 확장!

- 가중치 없는 그래프 = BFS 이용