[Python] Level 3. 가장 먼 노드

프로그래머스

 

문제 설명

1 ~ n번까지 번호가 적혀 있는 n개의 노드가 간선으로 연결되어 있을 때,

1번 노드에서 가장 멀리 떨어져 있는 노드의 개수를 구한다.

 

 

문제 풀이

(1) 사용한 알고리즘

BFS

 

(2) 시간복잡도

O(n)

 

(3) 설명

1. 최대 거리를 기억하는 변수(max_dist) & 1번 노드와의 최단거리를 담은 리스트(dist) 초기화

max_dist = 0
dist = [0 for _ in range(n + 1)]

✅ 편의를 위해 dist의 0번 인덱스는 사용하지 않으며, dist[k]는 1번 노드에서 k번 노드까지의 최단거리가 저장된다.

 

2. 인접리스트 만들기

출처) 프로그래머스

 

예를 들어 위 프로그래머스 테스트 케이스의 경우 아래와 같이 인접리스트를 만들 수 있다.

 

 

✅ 이 때 주의할 것은 2번과 5번 노드가 연결되어 있다면 2번 노드에 5번 노드 정보를 담고, 마찬가지로 5번 노드에도 2번 노드 정보를 담아야 한다.

 

파이썬으로 인접리스트를 만드는 코드는 아래와 같다.

# 인접 리스트 만들기
adj = [[] for _ in range(n + 1)]
for s, e in edge:
    adj[s].append(e)
    adj[e].append(s)

✅ dist와 마찬가지로 인접리스트에도 0번 인덱스는 사용하지 않는다.

 

3. 큐를 이용한 BFS 수행

파이썬의 deque를 이용해 큐를 구현한다.

처음 시작점인 1번 노드를 큐에 넣고, 큐에 노드가 있을 때까지 아래의 과정을 반복한다.

1. 큐에서 노드를 꺼낸다.
2. 꺼낸 노드와 직접적으로 연결된 노드를 탐색한다.
3. 현재 탐색한 노드의 dist가 0이라면 미방문한 상태이므로, dist를 업데이트해준 뒤, 해당 노드를 큐에 넣는다.
   ✅ visited 배열을 따로 둘 수 있지만 dist만으로 충분히 역할을 수행할 수 있기 때문에 메모리 낭비를 막을 수 있다.

from collections import deque

def bfs(adj, dist):
    global max_dist
    
    q = deque()
    q.append((1, 0))
    
    while q:
        curr, curr_dist = q.popleft()
        for v in adj[curr]:
            if v != 1 and dist[v] == 0:
                dist[v] = curr_dist + 1
                max_dist = max(max_dist, dist[v])
                q.append((v, dist[v]))

 

✅ 참고로 현재 방문한 노드의 거리를 업데이트할 때, 이 값이 가장 긴 거리인지 업데이트하는 로직을 중간에 추가해두었다.

✅ 이렇게 max_dist 변수를 거리를 구할 때마다 업데이트해주면, 나중에 max_dist 값과 동일한 거리를 갖는 노드만 필터링하기 용이하다.

max_dist = max(max_dist, dist[v])

 

4. 답 구하기

dist를 완전 탐색하여 앞서 구한 max_dist와 거리가 동일한 노드일 때 answer의 개수를 1개 증가시킨다.

answer = 0
for i in range(1, n + 1):
    if dist[i] == max_dist:
        answer += 1
            
return answer

 

(4) 풀이 코드

from collections import deque

def bfs(adj, dist):
    global max_dist
    
    q = deque()
    q.append((1, 0))
    
    while q:
        curr, curr_dist = q.popleft()
        for v in adj[curr]:
            if v != 1 and dist[v] == 0:
                dist[v] = curr_dist + 1
                max_dist = max(max_dist, dist[v])
                q.append((v, dist[v]))


def solution(n, edge):
    global max_dist
    max_dist = 0
    dist = [0 for _ in range(n + 1)]
    
    # 인접 리스트 만들기
    adj = [[] for _ in range(n + 1)]
    for s, e in edge:
        adj[s].append(e)
        adj[e].append(s)
        
    bfs(adj, dist)
    
    answer = 0
    for i in range(1, n + 1):
        if dist[i] == max_dist:
            answer += 1
            
    return answer