반응형
이 문제는 1번 정점에서 탐색을 시작하여 1번 정점에서 다른 정점에 이르기까지 얼마의 시간이 걸리는지 찾는 문제입니다.
위의 사진은 이 문제에서 힌트로 나와 있는 그림입니다.
이 그림과 같이 1번 정점을 기준으로 가장 멀리 떨어져 있는 정점들을 찾으면 됩니다.
이 그림에서는 4, 5, 6이 1에서 거리가 2로 가장 먼 정점들입니다.
그리고 거리가 같을 때는 정점의 번호가 가장 작은 정점에 숨으므로 숨어야 하는 정점은 4이고 거리는 2, 이 헛간과 같은 거리에 있는 헛간의 수는 3개입니다.
import java.io.*;
import java.util.*;
public class Main {
static int N;
static List<List<Integer>> l = new ArrayList<>();
static boolean[] visited;
static int[] lenArray;
static int maxLen = Integer.MIN_VALUE;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
visited = new boolean[N+1];
lenArray = new int[N+1];
for(int i = 0; i<=N; i++)
l.add(new ArrayList<>());
while(M-->0){
st = new StringTokenizer(br.readLine());
int A = Integer.parseInt(st.nextToken());
int B = Integer.parseInt(st.nextToken());
l.get(A).add(B);
l.get(B).add(A);
}
bfs();
int maxIdx = 0;
int maxCnt = 0;
for(int i = 1; i<=N; i++)
if(lenArray[i] == maxLen){
if(maxIdx == 0)
maxIdx = i;
maxCnt++;
}
System.out.println(maxIdx+" "+maxLen+" "+maxCnt);
}
static void bfs(){
Queue<Node> q = new LinkedList<>();
q.offer(new Node(1, 0));
visited[1] = true;
while(!q.isEmpty()){
Node a = q.poll();
maxLen = Math.max(maxLen, a.len);
lenArray[a.vertex] = a.len;
for(int i = 0; i<l.get(a.vertex).size(); i++){
int nextV = l.get(a.vertex).get(i);
if(visited[nextV])
continue;
q.offer(new Node(nextV, a.len+1));
visited[nextV] = true;
}
}
}
}
class Node{
int vertex, len;
Node(int vertex, int len){
this.vertex = vertex;
this.len = len;
}
}
bfs를 이용하면 쉽게 해결하실 수 있는 문제입니다.
반응형
'알고리즘 > 너비 우선 탐색(bfs)' 카테고리의 다른 글
백준 2638번 : 치즈 java (0) | 2022.07.26 |
---|---|
백준 24444번 : 알고리즘 수업 - 너비 우선 탐색 1 java (1) | 2022.07.17 |
백준 1743번 : 음식물 피하기 java (0) | 2022.07.10 |
백준 2660번 : 회장뽑기 java (0) | 2022.07.09 |
백준 2665번 : 미로만들기 java (0) | 2022.07.05 |
댓글