프로그래머스 level3 [가장 먼 노드] 파이썬

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

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

# 프로그래머스 가장 먼노드

def solution(n, edge):
    answer = 0
    visited = [0]*(n+1)
    cnt = [10000]*(n+1)
    link = [[] for _ in range(n+1)]
    for e in edge:
        a, b = e
        link[a].append(b)
        link[b].append(a)
    cnt[1] = 0

    def serach_dfs(node, count_):
        cnt[int(node)] = min(cnt[node], count_)
        if link[node]:
            for next_node in link[node]:
                if visited[next_node] == 0:
                    visited[next_node] = 1
                    serach_dfs(next_node, count_+1)
                    visited[next_node] = 0
    serach_dfs(1, 0)
    cnt.pop(0)
    M = max(cnt)
    answer=cnt.count(M)
    return answer

dfs가 익숙한 나는 생각없이 dfs로 해결하려고 하였다. 당연하게도 dfs로 한다면, 모든 경우의 수를 하나하나 다 따져야 하므로 시간초과가 발생한다. (바보)

 

 

 

 

 

# 프로그래머스 가장 먼노드

from collections import deque


def solution(n, edge):
    answer = 0
    visited = [0]*(n+1)
    cnt = [0]*(n+1)
    link = [[] for _ in range(n+1)]
    for e in edge:
        a, b = e
        link[a].append(b)
        link[b].append(a)

    def bfs(node, count_):
        q = deque([])
        q.append([node, count_])
        while q:
            node, count_ = q.popleft()
            for next_node in link[node]:
                if visited[next_node] == 0:
                    visited[next_node] = 1
                    q.append([next_node, count_+1])
                    cnt[next_node] = count_+1
        M = max(cnt)
        return cnt.count(M)
    visited[1] = 1
    answer = bfs(1, 0)
    return answer

 

bfs로 해결해야했다. (멋져)