티스토리 뷰
문제 출처:programmers.co.kr/learn/courses/30/lessons/49189
코딩테스트 연습 - 가장 먼 노드
6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3
programmers.co.kr
풀이
아무리 봐도 DFS로는 불가능해 보인다(혹시 가능할 수도?).. BFS로는 간단하게 해결할 수 있다.
다음 노드로 이동할 때마다 현재 위치가 제일 멀리 왔는지를 확인한다. 만약 제일 멀리 왔다면 유일하게 멀리 있는 노드이므로 answer는 1로 초기화한다. 그리고 현재 거리를 제일 먼 거리로 저장한다.
만약 제일 먼 거리가 현재 거리랑 같은 노드가 나오면 answer에 +1을 해주면 된다.
코드
'알고리즘' 카테고리의 다른 글
| 백준 - 동전0 (0) | 2021.02.13 |
|---|---|
| 프로그래머스 -단속카메라 (0) | 2021.02.04 |
| <프로그래머스> 단어 변환 (0) | 2021.01.30 |
| <프로그래머스> 섬연결하기 (0) | 2021.01.23 |
| <프로그래머스> 네트워크 (0) | 2021.01.19 |