📍문제

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

💻나의 풀이(BFS)

• 이코테에서 모든 간선의 비용이 동일할 때 BFS를 쓰는 것이 좋다는 것을 확인하고 BFS를 사용해주기로 했다!
• 여태 다른 DFS, BFS와 그래프를 저장하는 방식이 살짝 다른데, 비용을 1로 추가해주기로 했기 때문에 append하는 부분에 1도 추가해주기로 했다.
• 방문을 기록하는 노드마다 visited를 1씩 더해줘서 bfs함수에서 이를 리턴해준다. 이후 가장 멀리 있는 노드의 길이를 max_len이라 하며, 해당하는 max_len의 노드 개수가 몇개인지 리턴해주면 끝

from collections import deque

def bfs(graph, start, visited):
    q = deque([start])
    visited[start] = 1
    
    while q:
        v = q.popleft()
        for i in graph[v]:
            if visited[i[0]] == 0: 
                q.append(i[0])
                visited[i[0]] = visited[v] + 1                
    return visited
    
def solution(n, edge):
    answer = 0
    graph = [[] for _ in range(n+1)]
    visited = [0] * (n+1)
    
    for a, b in edge:
        graph[a].append([b, 1])
        graph[b].append([a, 1])
    
    n = bfs(graph, 1, visited) # 항상 1번 노드에서 시작

    max_len = max(visited)
    answer = visited.count(max_len)
    return answer

💻다른사람 풀이(다익스트라)

def solution(n, edge):
    graph =[[] for _ in range(n + 1) ]
    distances = [ 0 for _ in range(n) ]
    is_visit = [False for _ in range(n)]
    queue = [0]
    is_visit[0] = True
    for (a, b) in edge:
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)

    while queue:
        i = queue.pop(0)

        for j in graph[i]:
            if is_visit[j] == False:
                is_visit[j] = True
                queue.append(j)
                distances[j] = distances[i] + 1

    distances.sort(reverse=True)
    answer = distances.count(distances[0])

    return answer