[프로그래머스] 가장 먼 노드(Level3) (Python)

문제 출처 :

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

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

문제 풀이 :

• 자료구조 중 그래프를 이용하여 풀 수 있는 간단한 문제이다.(왜 level3인 걸까? 아마도 그래프라는 자료구조가 구현하기 쉽지 않아서 인가? 파이썬의 경우는 굉장히 쉽지만)
• 이런 류의 문제를 풀때 나는 cycle을 돌릴때마다 next_dq와 같이 다음에 순찰해야하는 후보들을 넣는 자료구조를 따로 정의하여 푼다. 이런식으로 풀어야 각 단계별로 거리를 더해주는것이 안 헷갈린다.(고수님들은 이런거 따로 안 만들고도 잘 푸신다.)

from collections import deque
from copy import deepcopy

def solution(n, edge):
    answer = 0
    graph ={}
    for i in range(1,n+1):
        graph[i]=[]
    for i in edge:
        graph[i[0]].append(i[1])
        if(i[0] not in graph[i[1]]):
            graph[i[1]].append(i[0])
    dist = [0]*(n+1)
    visited = [0]*(n+1)
    visited[1]=1
    dq = deque([])
    dq.extend(graph[1])
    cur_dist = 0
    while(True):
        # print(dq)
        # print(dist)
        next_dq = deque([])
        while(dq):
            cur_num = dq.popleft()
            if(visited[cur_num]==0):
                dist[cur_num] = cur_dist + 1
                visited[cur_num]=1
                next_dq.extend(graph[cur_num])
        cur_dist+=1
        if(not next_dq):
            break
        dq =deepcopy(next_dq)

    criterion_num = max(dist)
    for i in dist:
        if(i==criterion_num):
            answer+=1

    return answer