[JAVA]백준_6118_숨바꼭질

문제링크

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

6118번: 숨바꼭질

 

 

 

package BOJ;

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

public class Main_6118 {
    static int N,M;
    static ArrayList<Integer> list[];
    static boolean isVisited[];
    static int destination,distance,cnt;
    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()); //헛간의 개수
        M = Integer.parseInt(st.nextToken()); //M개의 양방향 길

       list = new ArrayList[N+1];
       isVisited = new boolean[N+1];

        for(int i=0;i<=N;i++) list[i] = new ArrayList<>();

        for(int i=0;i<M;i++){
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());

            list[start].add(end);
            list[end].add(start);
        }
        
        bfs();
        System.out.println(destination+" "+distance+" "+cnt);
    }

    private static void bfs() {
        Queue<int []> q = new LinkedList<>();
        isVisited[1] = true;
        q.offer(new int[]{1,0});

        while(!q.isEmpty()){
            int arr[] = q.poll();
            int now = arr[0];
            int next = arr[1];

            if(next > distance){
                distance = next;
                destination = now;
                cnt = 1;
            }
            else if(next == distance){
                if(destination > now) destination = now;
                cnt++;
            }

            for(int i=0;i<list[now].size();i++){
                int next_next = list[now].get(i);
                if(!isVisited[next_next]){
                    isVisited[next_next] = true;
                    q.offer(new int[]{next_next,next+1});
                }
            }
        }
    }

}

 

그래프를 이용한 간단한 bfs 문제였다.

bfs 함수를 통해 결과값을 구한다.

Queue에 현재 노드 값과 거리값을 넣어준다.

 

만약 현재 거리 값이(next) 결과값 거리(distance)보다 크면 제일 멀어질 수록 발냄새가 덜 나니까 

distance 값을 next로 갱신하여 주고 cnt 개수도 1로 다시 넣어준다.

 

혹은 만약 현재 거리 값 (next)와 결과값 거리가 같으면 cnt값만 +1해준다.

 

후에는 리스트를 하나하나 돌면서 

방문하지않았던 곳이면 큐에 다시 넣어주면서 확인을 한다.