[JAVA]백준 6118번: 숨바꼭질

 

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

6118번: 숨바꼭질

1. 문제 설명

 

문제

• 재서 기는 농장 헛간 들 중 하나에 숨어야 한다.
• 1번 헛간에서부터 거리가 멀어질수록 발 냄새가 감소할 때, 재서기의 발 냄새를 최대한 숨길 수 있는 헛간을 찾아보자.

조건

• 헛간의 개수는 N(2 <=N <=20,000) 개이며, 1부터 샌다.
• 어떤 헛간에서 다른 헛간으로는 언제나 도달 가능하다.
• 숨어야 하는 헛간 번호(만약 거리가 같은 헛간이 여러개라면 가장 작은 헛간 번호 출력), 그 헛간까지의 거리, 헛간과 같은 거리를 갖는 헛간의 개수를 출력
• 거리란 지나야 하는 길의 최소 개수이다.

 

2. 풀이

 

BFS로 풀 수 있는 문제이다.

 

Queue를 사용해서 헛간 1부터 시작해서 연결된 헛간들을 탐색해 나간다.

최소 거리를 구하는 문제이고, 여기서 거리란 지난 노드의 개수와 같기 때문에 이전에 탐색한 노드는 더 이상 탐색하지 않는다.

어떤 경우라 하더라도, 이전에 방문했을 때 이동 거리보다, 더 작게 이동할 수 있는 방법은 없다.

 

만약, 거리가 지난 노드의 개수가 아니라 다른 숫자가 주어진다면, 이전에 탐색한 노드도 탐색해야 할 수도 있다.

그럴 경우, 배열에 거리 값을 저장해두고, 그 거리보다 더 작게 이동할 수 있는 경우가 발견되면 다시 탐색을 시작하면 된다.

(이게 다익스트라 알고리즘이다.)

 

또한, 숨어야 하는 헛간 번호, 거리, 같은 거리를 갖는 헛간의 개수를 출력해야 하기 때문에 이를 확인해주는 것을 추가적으로 구현해야 한다.

 

*로직

1. ArrayList를 통해 연결된 헛간들 저장

2. Queue를 사용해서 BFS 탐색 시작

3. 1번 헛간부터 현재 헛간까지 이동하는 거리가 이전의 최댓값 보다 크다면 바꾼다.

4. 같다면, 같은 헛간의 개수를 증가시킨다.

 

3. 코드

// JAVA 11 , 메모리 : 33084KB, 시간 : 412ms

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

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int num, line;
        int one, two;
        int[] maxIdx = new int[3];
        Queue<Point> queue = new LinkedList<>();
        boolean[] visited;
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        StringTokenizer st = new StringTokenizer(br.readLine());

        num = Integer.parseInt(st.nextToken());
        line = Integer.parseInt(st.nextToken());

        visited = new boolean[num + 1];

        for (int x = 0; x <= num; x++) {
            list.add(new ArrayList<>());
        }

        for (int x = 0; x < line; x++) {
            st = new StringTokenizer(br.readLine());

            one = Integer.parseInt(st.nextToken());
            two = Integer.parseInt(st.nextToken());

            list.get(one).add(two);
            list.get(two).add(one);
        }


        queue.add(new Point(1, 0));
        visited[1] = true;

        while (!queue.isEmpty()) {
            Point now = queue.poll();

            // 최대 거리 계산
            if (now.move > maxIdx[1]) {
                maxIdx[0] = now.edge;
                maxIdx[1] = now.move;
                maxIdx[2] = 1;
            } else if (now.move == maxIdx[1]) {
                maxIdx[2]++;
                maxIdx[0] = Math.min(maxIdx[0], now.edge);
            }


            // 다음 노드 탐색
            for (int x : list.get(now.edge)) {
                if(visited[x])
                    continue;

                visited[x] = true;
                queue.add(new Point(x, now.move + 1));
            }
        }

        for(int x : maxIdx)
            sb.append(x).append(" ");

        System.out.println(sb);

    }


    public static class Point{
        int edge, move;

        Point(int edge, int move) {
            this.edge = edge;
            this.move = move;
        }
    }
}