[Java] 백준 6118 숨바꼭질 - 실버2

 

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

6118번: 숨바꼭질

 

 

추가 테스트 데이터

3 2
1 2
1 3
=> 2 1 2

 

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
  public static void main(String[] args) throws IOException {
    //입력 ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    int barnCnt = Integer.parseInt(st.nextToken());
    int roadCnt = Integer.parseInt(st.nextToken());

    List<List<Integer>> list = new ArrayList<>();
    for (int barn=0; barn<barnCnt+1; barn++)
      list.add(new ArrayList<>());

    for (int road =0; road<roadCnt; road++) {
      st= new StringTokenizer(br.readLine());
      int a = Integer.parseInt(st.nextToken());
      int b = Integer.parseInt(st.nextToken());
      list.get(a).add(b);
      list.get(b).add(a);
    }

    //거리 값을 저장할 배열 초기화. -1이면 방문하지 않은 것
    int[] distance = new int[barnCnt+1];
    Arrays.fill(distance, -1);

    //큐에 시작점 넣기
    Queue<Integer> queue = new LinkedList<>();
    queue.add(1);
    distance[1] = 0;

    while (!queue.isEmpty()) {
      int barn = queue.poll();

      //이어진 점들에 대해 방문여부 확인 후 큐에 넣기
      List<Integer> nextBarns = list.get(barn);
      for (Integer b: nextBarns) {
        if (distance[b] == -1) { //방문하지 않았다면
          distance[b] = distance[barn]+1;
          queue.add(b);
        }
      }
    }

    //출력
    int resultCnt = 0;
    int max = 0;
    int maxIdx = 0;
    for (int i =2; i<distance.length; i++) {
      int dis = distance[i];
      if (dis > max) {
        maxIdx = i;
        max = dis;
        resultCnt = 1;
      } else if (dis == max) {
        resultCnt ++;
      }
    }

    System.out.println("" + maxIdx + " " + max + " " + resultCnt);
  }
}

• List<List<Integer>> 에 그래프의 값들을 연결리스트 형태로 저장한다
  • 헛간과 연결된 헛간을 연결리스트로 저장하는 것(배열은 시간 오래걸림)
• int[] distance 배열을 만들어준다. 
  • 값이 -1이면 방문하지 않은 거고, -1이 아니면 방문한 것
  • 해당 헛간까지 가는 최소 거리를 저장한다
• 큐에 시작점인 1을 넣고 큐가 빌 때까지 반복한다
  • 큐에서 한 헛간값을 빼서
  • 해당 헛간과 이어진 List를 뽑아 방문여부를 확인 후, 방문하지 않았다면 거리를 +1 로 저장해주고 큐에 넣는다
• 출력은 distance 배열을 돌면서 최댓값을 찾는 방식으로 하였다.

 

 

 

이 문제는 갈 수 있는 최소 거리를 체크해야하기 때문에 bfs가 맞는 방법이다