[Level 3] 가장 먼 노드

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

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

---

접근

처음에 DFS로 각 노드를 방문하려고 했다. 하지만 현재 노드에서 깊이있게 탐색하기 때문에 1, 2, 3 노드가 모두 연결되어있다고하면 1->2->3으로 방문하여 모순이 발생하는 경우가 있을 수 있다.

따라서 현재 노드에서 주변 노드를 먼저 방문하는 BFS로 탐색하였다.

또한 2차원 리스트로 그래프를 표현하면 시간초과가 발생하였고 인접 리스트로 구현하였다.

 

구현

먼저 입력받은 간선의 정보를 통해 무방향 그래프를 표현하였다.

def solution(n, edge):
    answer = 0
    graph = [[] for _ in range(n)]

    for a, b in edge:
        a -= 1
        b -= 1
        graph[a].append(b)
        graph[b].append(a)

 

그 다음 BFS 탐색을 진행한다.

현재 노드와 연결된 노드를  탐색하여 길이를 증가시켜 방문했다는 표시를 한다.

q = deque()
q.append(0)
dist = [0 for _ in range(n)]
dist[0] = 1
    while q:
        front = q.popleft()
        for i in range(len(graph[front])):
            if dist[graph[front][i]] == 0:
                dist[graph[front][i]] = dist[front] + 1
                q.append(graph[front][i])

 

이후 가장 먼 노드의 거리를 찾고 이 거리에 해당되는 모든 노드를 카운트하여 answer에 저장한다.

max_dist = max(dist)
answer = dist.count(max_dist)

---

전체 코드

from _collections import deque
def solution(n, edge):
    answer = 0
    graph = [[] for _ in range(n)]

    for a, b in edge:
        a -= 1
        b -= 1
        graph[a].append(b)
        graph[b].append(a)

    q = deque()
    q.append(0)
    dist = [0 for _ in range(n)]
    dist[0] = 1
    while q:
        front = q.popleft()
        for i in range(len(graph[front])):
            if dist[graph[front][i]] == 0:
                dist[graph[front][i]] = dist[front] + 1
                q.append(graph[front][i])
    max_dist = max(dist)
    answer = dist.count(max_dist)
    return answer