[Python] 프로그래머스 49189.가장 먼 노드 (Lv.3)

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

프로그래머스

 

기본적인 BFS로 풀이가 가능한 문제입니다.

기본 문제라 Lv.3로 놓인거지 요즘 레벨로는 2레벨 중에서도 쉬운문제가 아닐까 싶습니다...

node의 갯수가 edge의 갯수보다 훨씬 많기 때문에 인접행렬 대신 인접리스트를 사용해 구현했습니다.

(node의 갯수가 2만개로 인접행렬로는 2만*2만 = 4억 사이즈가 됩니다.)

 

BFS를 이용해 시작점에서 부터의 거리가 한 칸씩 먼 노드들을 탐색했고, 매번 탐색한 노드의 갯수를 저장해서

더 탐색할 노드가 없는 경우엔 이전 턴에 탐색한 노드의 갯수를 리턴했습니다.

 

from collections import deque


def solution(n, edge):
    answer = 0
    adjList = [[] for i in range(n+1)]
    visited = [False]*(n+1)
    
    for i in edge:
        start = i[0]
        end = i[1]
        
        adjList[start].append(end)
        adjList[end].append(start)
    
    queue = deque()
    queue.append(1)
    visited[1] = True

    while(len(queue) != 0):
        answer = size = len(queue)
        
        for i in range(size):
            start = queue.popleft()
            
            for e in adjList[start]:
                if(not visited[e]):
                    visited[e] = True
                    queue.append(e)
    
    return answer


n = 6
vertexs = [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]

print(solution(n,vertexs))