알고리즘/문제풀이 - 프로그래머스

프로그래머스 레벨3 가장 먼 노드

문제 : https://programmers.co.kr/learn/courses/30/lessons/49189 서론 그래프 문제. 풀이 그래프를 탐색해서 가장 먼 노드들을 찾는다. 그래프 탐색 알고리즘은 DFS/BFS가 있는데, 최단거리 문제를 제외하고는 항상 DFS로 구현했던지라 이번에도 그렇게 했다. 그리고 문제 발생 3번 노드는 1번노드에서 한칸 떨어져 있지만 1 - 2 - 3순으로 탐색해서 2칸 떨어진것으로 인식할 수 있다. 방문할때 조건을 잘 설정해주면 될것 같기도 하지만 애초에 이런 문제가 없는 BFS로 다시 구현했다. 그래프를 만들고 노드들의 거리를 저장하는 배열을 만든다. BFS로 탐색하면서 방문할 노드의 거리는 이전 노드의 거리에서 +1한다. 그리고 노드의 거리 중 최대값은 변수에 저장하..

2019. 10. 28. 10:04