[프로그래머스] 가장 먼 노드 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

프로그래머스

 

1. 문제 설명

반응형

2. 풀이과정

해당 문제는 경로를 통해 노드를 탐색하며 1번 노드에서 각 노드까지 최단거리를 구한 뒤, 가장 멀리 떨어진 노드의 개수를 구하면 되는 문제이다.

1번 노드에서 각 노드까지 최단거리를 구하기 위해 BFS 알고리즘을 활용하여 각 노드를 탐색해 나간다.

연결된 노드를 탐색하며 다음 노드에서 최단거리는 이전 노드에서 최단거리에 1을 더해주면 된다.

거리를 저장할 리스트를 생성하고 연결된 노드를 탐색해 나갈 때마다 다음 노드에서의 최단거리를 저장해 나간다.

 

1. BFS 알고리즘을 활용할 때 deque 자료구조를 사용하기 위해 deque 모듈을 불러온다. from collections import deque
2. 그래프를 저장할 2차원 리스트를 생성한다. graph = [[] for _ in range(n + 1)]
3. 간선의 정보를 하나씩 불러와 for i in edge
   
   1. 그래프에 간선 정보를 저장한다. graph[i[0]].append(i[1])
   2. graph[i[1]].append(i[0])     
      
4. BFS 알고리즘을 활용한다. def bfs(start)
   
   1. 빈 queue를 생성하고 queue = deque()
   2. 시작 위치의 노드를 추가한다. queue.append(start)
   3. 시작 위치의 노드는 방문을 한 상태로 바꿔준다. visited[start] = True
   4. queue에 원소가 없을 때까지 반복하며 while (queue)
      1.  queue에서 제일 앞 원소를 가져온다. now = queue.popleft()
      2. 해당 원소에서 연결된 각 노드를 하나씩 불러오며 for i in graph[now]
         1. 만약 불러온 다음 노드가 아직 방문하지 않은 노드일 경우 if (not visited[i])
            1. 다음 노드의 최단거리를 노드의 최단거리에 1을 더하여 저장한다. distance[i] = distance[now] + 1
            2. 다음 노드를 queue에 추가한다. queue.append(i)
            3. 다음 노드도 방문을 한 상태로 바꿔준다. visited[i] = True
5. 각 노드의 방문 상태를 저장할 리스트를 생성하고 False로 초기화한다. visited = [False] * (n + 1)
6. 1번 노드에서 각 노드까지의 최단거리를 저장할 리스트를 생성하고 0으로 초기화한다. distance = [0] * (n + 1)
7. 시작 노드인 1번 노드를 기준으로 BFS 알고리즘을 수행한다. bfs(1)
8. BFS 알고리즘을 수행한 후 각 노드의 최단거리에서 가장 큰 값(가장 멀리 떨어진 노드)을 찾고 거리에서 가장 큰 값의 개수를 구한다. answer = distance.count(max(distance))

3. 소스코드

from collections import deque

def solution(n, edge):
    answer = 0
    
    graph = [[] for _ in range(n + 1)]
    for i in edge:
        graph[i[0]].append(i[1])
        graph[i[1]].append(i[0])
        
    def bfs(start):
        queue = deque()
        queue.append(start)
        visited[start] = True

        while (queue):
            now = queue.popleft()
            for i in graph[now]:
                if (not visited[i]):
                    distance[i] = distance[now] + 1
                    queue.append(i)
                    visited[i] = True
    
    visited = [False] * (n + 1)
    distance = [0] * (n + 1)
    bfs(1)

    answer = distance.count(max(distance))
    
    return answer