[백준 2644] 촌수계산 - JAVA

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

 

BFS

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int N = Integer.parseInt(br.readLine());
    StringTokenizer st = new StringTokenizer(br.readLine());

    int ST = Integer.parseInt(st.nextToken());
    int ED = Integer.parseInt(st.nextToken());
    // 서로 다른 두 사람의 번호가 주어진다. => 0촌 x
    int ans = -1;

    int M = Integer.parseInt(br.readLine());
    boolean[][] e = new boolean[N + 1][N + 1];

    for (int i = 0; i < M; i++) {
      st = new StringTokenizer(br.readLine());
      int f = Integer.parseInt(st.nextToken());
      int t = Integer.parseInt(st.nextToken());
      e[f][t] = e[t][f] = true;
    }

    boolean[] vst = new boolean[N + 1];
    Queue<int[]> q = new ArrayDeque<>();
    vst[ST] = true;
    q.offer(new int[]{ST, 0});

    while (!q.isEmpty()) {
      int[] info = q.poll();
      int cur = info[0];
      int d = info[1];

      if (cur == ED) {
        ans = d;
        break;
      }

      for (int i = 1; i <= N; i++) {
        if (!vst[i] && e[cur][i] && cur != i) {
          vst[i] = true;
          q.offer(new int[]{i, d + 1});
        }
      }
    }

    System.out.println(ans);
  }
}