백준 6118번 <숨바꼭질>

백준 알고리즘 6118번

https://www.acmicpc.net/problem/6118

6118번: 숨바꼭질

---

6118번

교외 농장에서 숨바꼭질을 하는 A와 B가 있다. 농장에는 헛간이 많고 그 중 하나에 A가 숨는다. A는 B가 1번 헛간부터 찾는 것을 알고 있다. 1번 헛간에서 가장 멀리 있는 헛간을 찾아라.

 

입력으로 첫 줄에 헛간의 총 개수 n과 헛간 간의 경로의 개수 m이 들어온다. 그 다음 m개의 줄에 걸쳐 각 경로의 정보가 주어진다. 해당 정보는 i j 로 이루어져 있는데 이는 i번 헛간에서 j번 헛간으로의 길과 j번 헛간에서 i번 헛간으로의 길이 존재한다는 의미이다.

 

출력으로 1번 헛간에서 가장 멀리 있는 헛간을 구하고 해당 헛간의 번호와 그 헛간 까지의 거리, 그 헛간과 같은 거리에 있는 헛간의 개수를 출력하면 된다. (거리가 같은 헛간이 여러 개라면 가장 작은 헛간 번호를 출력한다.)

---

문제 해결

BFS로 1번 헛간부터 다른 헛간까지의 거리를 모두 구했다.

이미 구한 헛간의 거리는 건들이면 안된다.

헛간까지의 거리를 구할 때, 가장 먼 거리 far를 기억해둔다. 거리를 모두 구한 다음, 거리 배열을 뒤에서부터 모두 탐색하여 거리가 far와 같으면 count하고 헛간 번호를 기억해두었다. 뒤에서부터 탐색한 이유는 거리가 같은 헛간일 경우 가장 작은 헛간 번호를 출력해야 하기 때문이다.

---

코드

package bj6118;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] inArr = br.readLine().split(" ");
		int n = Integer.parseInt(inArr[0]);
		int m = Integer.parseInt(inArr[1]);
		ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
		int[] dist = new int[n + 1];
		for (int i = 0; i < n + 1; i++) {
			graph.add(new ArrayList<Integer>());
			dist[i] = 0;
		}

		Queue<Integer> queue = new LinkedList<>();
		for (int i = 0; i < m; i++) {
			inArr = br.readLine().split(" ");
			int a = Integer.parseInt(inArr[0]);
			int b = Integer.parseInt(inArr[1]);

			graph.get(a).add(b);
			graph.get(b).add(a);
			if (a == 1) {
				queue.add(b);
				dist[b] = 1;
			}
			if (b == 1) {
				queue.add(a);
				dist[a] = 1;
			}
		}
		int far = 1;
		while (!queue.isEmpty()) {
			int pop = queue.poll();
			ArrayList<Integer> temp = graph.get(pop);
			for (int i = 0; i < temp.size(); i++) {
				if (dist[temp.get(i)] > 0 || temp.get(i) == 1) {
					continue;
				}
				dist[temp.get(i)] = dist[pop] + 1;
				far = Math.max(far, dist[temp.get(i)]);
				queue.add(temp.get(i));
			}
		}
		int cnt = 0;
		int answer = 0;
		for(int i = n; i > 1; i--) {
			if(dist[i] == far) {
				answer = i;
				cnt++;
			}
		}
		System.out.println(answer + " " + far + " " + cnt);
	}

}

---

결과

---