[프로그래머스] 가장 먼 노드(python)

[프로그래머스] 가장 먼 노드(python)

문제 출처

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

설명

그래프가 주어지고, 1번 노드부터 가장 먼 거리, 최단 경로의 노드의 갯수가 몇개인지 세는 문제이다.

처음에 dfs로 하려다 보니 최단 경로가 안나와서 bfs로 방법을 바꾸었다.

이 문제의 포인트는 1번 노드부터 몇 단계를 거친건지 알기 위한 방법과, 시간복잡도 해결이다.

몇 단계를 거친 것인지 알기 위해 딕셔너리를 사용해 이전 노드가 몇 단계를 거친 것인지 알아내는 방식을 사용했고,

bfs를 인접 리스트 방식으로 구현하여 시간 복잡도를 줄였다.

여태 모든 문제를 2차원 배열로 풀었는데 인접 리스트 방식을 활용해서 푸는 방법을 배울 수 있었다.

코드

# 출처 : https://programmers.co.kr/learn/courses/30/lessons/49189 from collections import deque def solution(n, edge): # 그래프 그리기(시간복잡도 때문에 인접리스트 방식으로 구현해주어야 함) answer = [] graph = {} for i in range(n): graph[i] = [] for road in edge: graph[road[0]-1].append(road[1]-1) graph[road[1]-1].append(road[0]-1) visit = [0 for i in range(n)] queue = deque([0]) visit[0] = 1 count = 1 # 몇 계층인지 알기 위한 딕셔너리 layerDict = { 0: 0 } # bfs로 구현 while(queue): curNode = queue.popleft() # 이번 층(단계)은 큐에서 꺼낸 노드의 층보다 1단계 더 thisLayer = layerDict[curNode]+1 for j in (graph[curNode]): if(visit[j] == 0): queue.append(j) layerDict[j] = thisLayer visit[j] = 1 count += 1 for key in layerDict: answer.append(layerDict[key]) maxNo = answer[-1] return answer.count(maxNo)

from http://ssookveloper.tistory.com/15 by ccl(A) rewrite - 2021-09-20 19:00:26