(프로그래머스) 코딩테스트 연습 - 그래프 - 가장 먼 노드 (Python)

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

코딩테스트 연습 - 가장 먼 노드 | 프로그래머스

문제 설명

n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.

노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 노드의 개수 n은 2 이상 20,000 이하입니다.
• 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.
• vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.

제가 통과한 코드

from collections import defaultdict, deque

def solution(n, edge):
    answer = 0
    
    dists = {i:0 for i in range(1, n+1)}
    edges = defaultdict(list)
    
    for u, v in edge:
        edges[u].append(v)
        edges[v].append(u)
        
    q = deque(edges[1])
    dist = 1
    while q :
        size = len(q)
        for i in range(size):
            v = q.popleft()
            
            if dists[v] == 0:
                dists[v] = dist
                for w in edges[v]:
                    q.append(w)
                     
        dist += 1
    
    del dists[1]
    
    max_dist = max(dists.values())
    for i in dists.values():
        if max_dist == i :
            answer+=1 
    
    return answer

풀이

참고 - https://dailyheumsi.tistory.com/124

이 문제는 bfs문제로 1에서 부터 각 노드 간의 거리를 다 구하는 문제입니다.

그리고 한 번이라도 방문한 경우에는 방문하지 않도록 합니다.

또 한, 1과 1의 거리도 나오기 때문에 마지막에 dists에서 1과 1의 거리는 삭제해줍니다.

 

느낀점

사실 그래프 문제는 빈도가 낮다고 하는데, 전 어떤 대기업과 중소기업에서 코딩테스트를 치는데 그래프 문제가 나오더라구요.. 

다른 문제는 끄적여 볼 수라도 있었는데, 그래프는 어떻게 접근해야하는지 조차 감이 안와서 이번기회에 한번 문제를 접해봤습니다.

물론, 풀진 못하고 어떤식으로 접근하는지 다른사람의 코드를 참고하여 디버깅해보면서 이해를 했습니다.

이런 문제는 여러번 풀어야 감이 올 것 같네요... ㅠㅠ

 

코드에서는 뭔가 한번 방문한 경우 방문하지 않도록 하기 위해 True, False나 0과 1로 리스트 또는 딕셔너리로 만들어서 접근할 줄 알았는데, 바로 거리를 표현하면서 나타내는 코드를 보고 또 한 번 신기함을 느꼈습니다....

 

물론 다른 사람들의 코드를 보면, 위와 같은 흐름이지만 2차원 배열로 오직 list만 활용하고, 방문 표시를 나타내는 list까지 만들어서 알고리즘을 짠 경우도 몇 보이는 것 같습니다. 

 

멀고도 험한 알고리즘의 세계네요..