프로그래머스 - 가장 먼 노드 (DFS, BFS) Python

문제

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

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

 

 

풀이

• BFS 탐색
• 인접행렬 : 노드 간의 연결 여부 check
• visited : 각 노드에 count로 방문하기까지 거쳐온 횟수

 

 

코드

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

from collections import deque

def bfs(v, visited, adj):
    count = 0
    q = deque([[v, count]]) #노드, 몇 번 거쳐왔는지 count
    while q:
        value = q.popleft()
        v = value[0]
        count = value[1]
        if visited[v] == -1: #아직 방문 X 인 곳 탐색
            visited[v] = count 
            count += 1 #횟수 증가
            for e in adj[v]: #이 노드와 연결된 다른 노드들 삽입
                q.append([e, count])

def solution(n, edge):
    answer = 0
    visited = [-1] * (n + 1) #방문 여부 check
    adj = [[] for _ in range(n + 1)] #인접리스트
    for e in edge:
        x = e[0] #연결노드 쌍 중 1번째
        y = e[1] #연결노드 쌍 중 2번째
        adj[x].append(y) #연결리스트 양측 두 노드 모두 연결 입력
        adj[y].append(x)
    bfs(1, visited, adj)
    return visited.count(max(visited))