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

코딩테스트 - 그래프 - 가장 먼 노드 [Level3]

문제링크 : 가장 먼 노드

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

 

문제풀이

그래프 문제입니다.

 

기존 BFS 풀이를 가지고 풀면 

7,8,9 케이스에서 "시간 초과"를 만나게 됩니다.

 

그러기 위해서 그래프의 방법 중

"인접 행렬" 이 아닌 "인접 리스트"를 사용해야 합니다.

 

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

위 행렬 생성 코드 작성만 해놔도 시간 초과가 걸립니다.

 

인접 행렬의 경우 연결할 수 있는 모든 경우의 수를 체크를 하고

인접 리스트는 연결된 경우의 수만 체크하기 때문에 

노드가 많고 연결이 적은 경우 시간 차이가 많이 납니다.

 

linked_list 안에 연결된 노드들을 넣어 체크를 진행합니다.

 

[Python] 가장 먼 노드

 

가장 인기 많은 답변

[Most Liked Code] 가장 먼 노드

• 방식은 비슷하나 따로 visit 행렬을 사용했습니다.
  • 가장 먼 노드만 파악하면 되기 때문에 distances에서 방문 처리해도 된다고 생각합니다.