최단경로 / BFS - 숨바꼭질 - Java

1. 문제

동빈이는 숨바꼭질을 하면서 술래로부터 잡히지 않도록 숨을 곳을 찾고 있습니다. 동빈이는 1 ~ N번까지의 헛간 중에서 하나를 골라 숨을 수 있으며, 술래는 항상 1번 헛간에서 출발합니다. 전체 맵에는 총 M개의 양방향 통로가 존재하며, 하나의 통로는 서로 다른 두 헛간을 연결합니다. 또한 전체 맵은 항상 어떤 헛간에서 다른 어떤 헛간으로 도달이 가능한 형태로 주어집니다.
동빈이는 1번 헛간으로부터 최단 거리가 가장 먼 헛간이 가장 안전하다고 판단하고 있습니다. 이때 최단 거리의 의미는 지나야 하는 길의 최소 개수를 의미합니다. 동빈이가 숨을 헛간의 번호를 출력하는 프로그램을 작성하세요.

입력 조건

1. 첫째 줄에는 N과 M이 주어지며, 공백으로 구분합니다. (2 <= N <= 20,000), (1 <= M <= 50,000)
2. 이후 M개의 줄에 걸쳐서 서로 연결된 두 헛간 A와 B의 번호가 공백으로 구분되어 주어집니다. (1 <= A, B <= N)

출력 조건

첫 번째는 숨어야 하는 헛간 번호를(만약 거리가 같은 헛간이 여러 개면 가장 작은 헛간 번호를 출력합니다.),
두 번째는 그 헛간까지의 거리를, 세 번째는 그 헛간과 같은 거리를 갖는 헛간의 개수를 출력해야 합니다.

입력 예시

6 7
3 6
4 3
3 2
1 3
1 2
2 4
5 2

출력 예시

4 2 3

2. 풀이

이 문제는 최단 경로, BFS 두가지 방법으로 풀 수 있다.
BFS로 풀 수 있는 이유는 거리가 1이기 때문이다. 가중치가 따로 주어지지 않기 때문에 BFS로 풀 수 있는 것이다.

두 방법의 차이는 while(!~.isEmpty())이다.

✨최단 경로

다익스트라로 PriorityQueue를 이용해서 구해준다.

✨BFS

Queue를 이용하며 check배열을 통해서 방문한적이 있는지 확인하였다.

3-1. [최단경로] 코드

import java.util.*;
import java.io.*;

public class 최단거리_숨바꼭질 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		ArrayList<ArrayList<Node>> list = new ArrayList<>();
		int d[] = new int[N+1];
		PriorityQueue<Node> pq = new PriorityQueue<>();
		
		for(int i = 0; i <= N; i++) {
			list.add(new ArrayList<Node>());
			d[i] = (int)1e9;
		}
		
		for(int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int A = Integer.parseInt(st.nextToken());
			int B = Integer.parseInt(st.nextToken());
			
			list.get(A).add(new Node(B, 1));
			list.get(B).add(new Node(A, 1));
		}
		
		d[1] = 0;
		pq.add(new Node(1, 0));
		
		while(!pq.isEmpty()) {
			Node node = pq.poll();
			
			if(d[node.num] < node.dis) continue;
			
			for(int i = 0; i < list.get(node.num).size(); i++) {
				int nextNum = list.get(node.num).get(i).num;
				int cost = d[node.num] + list.get(node.num).get(i).dis;
				if(cost < d[nextNum]) {
					d[nextNum] = cost;
					pq.add(new Node(nextNum, cost));
				}
			}
		}
		
		int minIndex = 0;
		int maxDistance = 0;
		int countSame = 0;
		
		for(int i = 2; i <= N; i++) {
			if(d[i] != (int)1e9 && (maxDistance) < d[i]) {
				maxDistance = d[i];
				minIndex = i;
				countSame = 1;
			} else if(maxDistance == d[i]) {
				countSame += 1;
			}
		}
		System.out.println(minIndex + " " + maxDistance + " " + countSame);

	}
	
	public static class Node implements Comparable<Node> {
		int num;
		int dis;
		
		public Node(int num, int dis) {
			this.num = num;
			this.dis = dis;
		}
		
		@Override
		public int compareTo(Node other) {
			return Integer.compare(this.dis, other.dis);
		}
	}

}

3-2. [BFS] 코드

import java.util.*;
import java.io.*;

public class 최단거리_숨바꼭질_BFS {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		ArrayList<ArrayList<Node>> list = new ArrayList<>();
		int d[] = new int[N+1];
		boolean check[] = new boolean[N+1];
		Queue<Node> q = new LinkedList<>();
		
		for(int i = 0; i <= N; i++) {
			list.add(new ArrayList<Node>());
			d[i] = (int)1e9;
		}
		
		for(int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int A = Integer.parseInt(st.nextToken());
			int B = Integer.parseInt(st.nextToken());
			
			list.get(A).add(new Node(B, 1));
			list.get(B).add(new Node(A, 1));
		}
		
		d[1] = 0;
		check[1] = true;
		q.add(new Node(1, 0));
		
		while(!q.isEmpty()) {
			Node node = q.poll();
			
			if(d[node.num] < node.dis) continue;
			
			for(int i = 0; i < list.get(node.num).size(); i++) {
				int nextNum = list.get(node.num).get(i).num;
				int cost = d[node.num] + list.get(node.num).get(i).dis;
				
				if(check[nextNum]) continue;
				if(cost < d[nextNum]) {
					d[nextNum] = cost;
					check[nextNum] = true;
					q.add(new Node(nextNum, cost));
				}
			}
		}
		
		int minIndex = 0;
		int maxDistance = 0;
		int countSame = 0;
		
		for(int i = 2; i <= N; i++) {
			if(d[i] != (int)1e9 && (maxDistance) < d[i]) {
				maxDistance = d[i];
				minIndex = i;
				countSame = 1;
			} else if(maxDistance == d[i]) {
				countSame += 1;
			}
		}
		System.out.println(minIndex + " " + maxDistance + " " + countSame);

	}
	
	public static class Node{
		int num;
		int dis;
		
		public Node(int num, int dis) {
			this.num = num;
			this.dis = dis;
		}
	}

}