문제

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

n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.

노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.

제한 사항

• 노드의 개수 n은 2 이상 20,000 이하입니다.
• 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.
• vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.

입출력 예시

위의 예시를 그래프로 표현하면 아래와 같다.

아이디어

👎 Error_런타임에러, 시간초과
1번 노드로 부터 떨어진 거리를 알아야 하기 때문에 node라는 리스트를 만들어서 각 노드까지 거리를 담는다.
1. 1번과 바로 연결된 노드들은 node리스트에 1을 넣는다.
2. 그렇지 않은 경우, 우선 1에서 갈 수 있는 노드를 ans에 추가한 후, 그 노드에서 갈 수 있는 다른 노드를 계속 추가한다.
3. 더 이상 갈 수 있는 노드가 없다면 해당 노드를 ans리스트에서 제거한 후 반복한다.
4. 마지막에 갈 노드가 들어온다면 반복문을 종료한다.
5. 만약 ans리스트에 1이 다시 등장한다면 더 짧은 가깝게 갈 수 있으므로 앞을 제거한다.

[#Error]solution함수_python

런타임 에러, 시간 초과

def solution(n, edge):
    answer = 0
    node = [0] * (n + 1)
    edge.sort()
    for i in range(2, n + 1):
        if [1, i] in edge or [i, 1] in edge:  # 1과 바로 이어진 경우
            node[i] = 1
        else:  # 그렇지 않은 경우 => 1과 바로 이어지지 않은 경우
            ans = []
            edge_chk = edge.copy()

            for k in range(len(edge_chk)):
                if 1 in edge_chk[k]:
                    ans.append(edge_chk[k])
                    edge_chk.remove(edge_chk[k])
                    break
            while i not in ans[-1]:  # i = 4
                for j in range(len(edge_chk)):
                    if max(ans[-1]) in edge_chk[j]:
                        ans.append(edge_chk[j])
                        edge_chk.remove(edge_chk[j])
                        break
                    if j == len(edge_chk) - 1:
                        ans.pop()
            for c in range(len(ans)-1, 0, -1):
                if 1 in ans[c]:
                    ans = ans[c:]
            node[i] = len(ans)
    for i in node:
        if i == max(node):
            answer += 1

    return answer

[#Clone] solution함수_python

✅ 1. 각 노드에 연결된 정보를 저장할 graph라는 리스트를 만든다.
2. graph는 양방향이므로 둘 다 저장을 시켜둔다.
3. 1번 노드부터 출발하므로 각 거리를 담고있는 route[1]을 1로 만들고 queue에 추가한다.
4. queue가 비어있을 때까지 반복을 하는데 거리(route)가 0인 경우에 해당 노드를 추가하고 해당 노드에서 부터 갈 수 있는 노드까지의 거리를 계산해서 route에 추가한다.
5. route가 모두 계산되면(queue가 비어있으면) answer을 구한다.

from collections import deque

def solution(n, edge):
    route = [0] * (n+1)
    graph = [[]for _ in range(n+1)]
    for i in range(len(edge)):
        graph[edge[i][0]].append(edge[i][1])
        graph[edge[i][1]].append(edge[i][0])
   
    route[1] = 1
    queue = deque()
    queue.append(1)

    while queue:
        node = queue.popleft()
        for i in graph[node]:
            if route[i] == 0:
                queue.append(i)
                route[i] = route[node] + 1

    return route.count(max(route))

clone코드 출처