문제#
- 링크로 대체
풀이 및 주저리..
프로그래머스에 있는 그래프 문제중 첫번째 문제인 가장 먼 노드이다. 그래프..? BFS? 같이 공식적으로 머리가 진행되면서 문제를 어떻게 풀어야할까 접근했다. 먼저 각 노드에서 간선들을 맵 형태로 저장했고 반대일 경우도 생각해야하므로 맵에 들어있는 노드별로 간선들을 넣어주었다. 그 후에는 BFS를 활용해서 각 선에서 갈 수 있는 거리를 배열로 저장해준다음 마지막에 배열을 순회하면서 최대값일때의 개수를 세어주었다. 처음에 기본 값 0일때 해결하려다가 노드가 1일때의 처리가 잘 되지 않아서 배열의 초기값을 -1로 설정해주고 진행하게되었다. 리팩토링 하다보면 좀 더 좋은 코드가 나올 수 있을 것 같다.
코드
package programmers.graph;
import java.util.*;
public class FarthestNode {
public int solution(int n, int[][] edge) {
int answer = 0;
int[] numCntArr = new int[n + 1];
Arrays.fill(numCntArr,-1);
numCntArr[1] = 0;
HashMap<Integer, Set<Integer>> numMap = new HashMap<>();
Queue<Integer> que = new LinkedList<>();
que.add(1);
for (int[] node : edge) {
Set<Integer> list = numMap.getOrDefault(node[0], new HashSet<>());
Set<Integer> revList = numMap.getOrDefault(node[1], new HashSet<>());
list.add(node[1]);
revList.add(node[0]);
numMap.put(node[0], list);
numMap.put(node[1], revList);
}
while (!que.isEmpty()) {
int p = que.poll();
Set<Integer> numSet = numMap.get(p);
for (Integer i: numSet) {
if(numCntArr[i] != -1) continue;
numCntArr[i] = numCntArr[p] + 1;
que.add(i);
}
}
int temp = 0;
for(int i = 1 ; i< numCntArr.length; i++){
if(numCntArr[i] > temp){
answer = 1;
temp = numCntArr[i];
}else if(temp == numCntArr[i]){
answer++;
}
}
return answer;
}
}기억에 남길 것!
- 시작의 예외처리 유의