가장 먼 노드 (프로그래머스 고득점 키트)

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

프로그래머스

 

그래프를 탐색해서 1번 노드와 가장 먼 거리에 있는 노드들의 갯수를 세는 문제다.

 

기본적으로 문제에서 주어진 edge들로 인접 리스트를 만들어서 dfs나 bfs같은 탐색알고리즘을 적용하며 되는 비교적 간단한 문제이다. 이 문제에는 bfs를 적용해서 풀어보았다.

---

1 번 노드와 거리를 저장하기 위해 dist라는 리스트를 만들었고 거리를 측정하기 위해 인접 노드로 이동할 때마다 1씩 증가시켜주면 된다. 특히 dist를 0으로 초기화해서 인접 노드까지 거리가 0인 노드들은 처음 방문한 노드로 생각하면 되기에 따로 visited 배열을 생략했다.

while q:
    node = q.popleft()
    for el in adj[node]:
        if dist[el] == 0:
            q.append(el)
            dist[el] = dist[node] + 1

 

이후 가장 먼 거리를 구하기 위해 max 함수를 사용해서 가장 먼 거리를 구해주고 dist 배열에서 가장 먼 거리를 찾을 때마다 cnt 변수에 1씩 더해주면 된다.

max_dis = max(dist)
    for i in dist:
        if i == max_dis:
            cnt += 1

 

전체코드

from collections import deque

def solution(n, edge):
    adj = [[] for _ in range(n+1)]
    dist = [0]*(n+1)
    q = deque()
    cnt = 0
    
    for e in edge:
        a, b = e
        adj[a].append(b)
        adj[b].append(a)
        
    q.append(1)
    dist[1] = 1
    
    while q:
        node = q.popleft()
        for el in adj[node]:
            if dist[el] == 0:
                q.append(el)
                dist[el] = dist[node] + 1
                             
    max_dis = max(dist)
    for i in dist:
        if i == max_dis:
            cnt += 1
    return cnt

---

일반적인 그래프 문제인데, 오래동안 문제를 안 풀다보니 디테일에서 실패를 여러번 겪었다. 문제는 하루에 한번씩은 꾸준히 풀여야겠다.. ㅠㅠ