문제
n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.
노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.
제한사항
- 노드의 개수 n은 2 이상 20,000 이하입니다.
- 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.
- vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.
해결방안
이 문제는 bfs를 이용하여 풀면 쉽게 풀수 있는 문제이다. bfs는 너비우선탐색으로 근접해 있는 노드들을 다 찾아보고 찾아 본 노드들을 기준으로 다시 근접한 노드들을 찾는 것이다.
1
2 3 4
7
8
5 6
이 순서대로 노드를 탐색한다 -> 처음에 1과 관련된 노드들을 모두 탐색하고 탐색이 끝난 뒤 2와 관련된 노드를 탐색, 3과 관련된 노드를 탐색, 4와 관련된 노드를 탐색한다.
----------------------------------------------------------------------------------------------------------
1. 방문했는지를 위한 int형의 배열을 만들고 bfs를 위한 queue를 만든다.
2. 처음은 방문이 되는 것이므로 int형 배열에 1에 1을 넣고 queue에 1을 넣는다.
3. 큐가 비어있지 않으면 while문을 반복하고 cur에 현재 queue의 처음 값을 뽑아낸다.
4. edge의 원소의 0번째와 1번째와 비교하여 둘 중에 하나가 cur의 값과 같고 다른 값을 index로 rep의 값이 0이면 queue에 같지 않은 값을 넣고 rep에 현재 값을 index로 하는 rep의 값에서 1을 더한 값을 넣어준다.
5. 오름차순으로 정렬시키고 마지막 값과 같은 값의 개수를 answer로 리턴한다.
코드
package programmers_3;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
public class farthest_node {
public static void main(String[] args) {
int n = 6;
int[][] edge = {{3,6},{4,3},{3,2},{1,3},{1,2},{2,4},{5,2}};
farthest_node s= new farthest_node();
System.out.println(s.solution(n,edge));
}
public int solution(int n, int[][] edge){
int answer = 0;
//방문했는지 확인하기 위한 배열
int[] rep = new int[n+1];
rep[1] = 1;
//bfs를 위한 큐
Queue<Integer> queue = new LinkedList<>();
queue.add(1);
while(!queue.isEmpty()){
int cur = queue.poll();
for(int i = 0; i< edge.length;i++){
if(cur == edge[i][0] && rep[edge[i][1]]==0){
rep[edge[i][1]] = rep[cur] + 1;
queue.add(edge[i][1]);
}
if(cur == edge[i][1] && rep[edge[i][0]] == 0){
rep[edge[i][0]] = rep[cur] + 1;
queue.add(edge[i][0]);
}
}
}
Arrays.sort(rep);
int max = rep[rep.length-1];
for(int i : rep){
if(i == max) answer++;
}
return answer;
}
}
댓글