[프로그래머스] 가장 먼 노드 (Lv 3) 2트

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

예에전에 굉장히 삽질했던 문제 같은데,

이번에는 너무 수월하게 풀어버렸다.

그냥 bfs로도 풀린다. 아이디어는 간단하다

(1) 양방향 그래프니까, 그냥 양방향을 다 넣어준다.
(2) 방문을 하되, 거리를 저장한다. 어차피 그리디하게 생각하면 bfs가 각 노드 최단 방문거리다.
즉, 이미 방문한 적이 있으면 그게 이미 최단거리라서 더 뭘 생각할 거리가 없다.!

다시 말해, visited를 True/False가 아니라 -1로 해놓고 0 이상의 거리면, 방문했음으로 판정하게
visited를 유연하게만 바꿔주면 되는 엄청나게 쉬운 문제다. 헤매지 말자.

다익스트라 그런거 필요 없다. 이 문제. 쉽게 생각하자.

# bfs idea : 점별 거리를 넣는다. 거리가 가장 최대인 index를 뽑아낸다.
# 노드 개수가 2만개이므로 충분할 것이다.
# 즉, visited 행렬을 True/False가 아니라 -1로 하고, 0 이상일 경우를 기준으로 한다.
from collections import deque
def bfs(vertex, visited):
    queue = deque()
    visited[0] = 0
    # 번호, dist
    queue.append((1, 0))
    
    while queue:
        cur_v, dist = queue.popleft()
        next_v = vertex[cur_v - 1]
        for n in next_v:
            if visited[n-1] == -1:
                visited[n-1] = dist + 1
                # dist 빼먹지 말고.
                queue.append((n, dist+1))
    return visited
def solution(n, vertex):
    # visited : 1과의 거리를 넣을 계획
    visited = [-1]*n
    vertex_list = [[] for _ in range(n)]
    for v in vertex:
        # 그래프를 역방향으로 타고 돌아가는게 베스트일 수 있어서, 그걸 조심해야함
        # 방향 그래프가 아니다! 따라서 양 방향을 다 넣어줘야 한다.
        vertex_list[v[0]-1].append(v[1]) 
        vertex_list[v[1]-1].append(v[0])
    # 최단거리 = bfs로 가면 최단거리가 나오게 된다.
    answer = bfs(vertex_list, visited)
    max_dist = max(answer)
    return answer.count(max_dist)