쌓고 쌓다
[프로그래머스] 가장 먼 노드 Java 풀이 및 해설 본문
https://school.programmers.co.kr/learn/courses/30/lessons/49189#qna
풀이 방법
BFS로 어떤 노드를 방문할때마다 탐색 비용을 기록한다.
최대 비용과 동일하다면 최대 비용과 동일한 비용으로 이동이 가능한 노드이므로
answer++한다.
최대 비용과 다르다면 더 큰 비용으로 이동해야하므로
answer=1으로 갱신해준다.
BFS라서 최대 비용이 다르다면 항상 이전보다 더 큰 비용이다.
전체 코드
import java.util.*;
class Solution {
public class Node {
int num; // 노드 번호
int cost; // 1부터 이 노드까지 걸리는 비용
public Node(int num, int cost) {
this.num = num;
this.cost = cost;
}
}
public int solution(int n, int[][] edge) {
int answer = 0;
List<Integer>[] list = new ArrayList[n+1];
for(int i=0; i<list.length; i++) {
list[i] = new ArrayList<>();
}
// list[x]에는 노드 x에서 연결된 노드들이 리스트로 담겨있다.
for(int i=0; i<edge.length; i++) {
list[edge[i][0]].add(edge[i][1]);
list[edge[i][1]].add(edge[i][0]);
}
boolean visit[] = new boolean[20001];
Queue<Node> q = new LinkedList<Node>();
q.add(new Node(1, 0));
visit[1] = true;
// 최대 거리
int maxCost = 0;
while(q.size() != 0) {
int num = q.peek().num;
int cost = q.peek().cost;
q.remove();
// 최대 거리랑 동일하다면 최대 거리로 갈 수 있는 노드가 더 있다는 것
if(maxCost == cost)
answer++;
else { // 최대 거리와 다르다면(BFS라 최대 거리가 다르다면 항상 이전 최대거리보다 큼) 더 큰 최대 거리인 것
answer = 1;
maxCost = cost;
}
for(int i=0; i<list[num].size(); i++) {
int nextNum = list[num].get(i);
if(visit[nextNum] == false) {
visit[nextNum] = true;
q.add(new Node(nextNum, cost+1));
}
}
}
return answer;
}
}
'알고리즘 > 프로그래머스' 카테고리의 다른 글
[프로그래머스] 디스크 컨트롤러 Java 풀이 및 해설 (0) | 2024.05.18 |
---|---|
[프로그래머스] 여행경로 Java 풀이 및 해설 (0) | 2024.05.16 |
[프로그래머스] 섬 연결하기 Java 풀이 및 해설 (0) | 2024.05.14 |
[프로그래머스] 징검다리 건너기 Java 풀이 및 해설 (0) | 2024.05.14 |
[프로그래머스] 보석 쇼핑 Java 풀이 및 해설 (0) | 2024.05.13 |
Comments