[BOJ] 2664 촌수계산

[문제]

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

 

 

 

[소스 코드]

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

public class Solution {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int n = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		int x = Integer.parseInt(st.nextToken());
		int y = Integer.parseInt(st.nextToken());
		boolean[][] connect = new boolean[n+1][n+1];
		int m = Integer.parseInt(br.readLine());
		for(int i=0;i<m;i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			connect[a][b] = connect[b][a] = true;
		}
		Queue<int[]> q = new LinkedList<>();
		boolean[] visit = new boolean[n+1];
		q.offer(new int[] {x,0});
		visit[x] = true;
		while(!q.isEmpty()) {
			int[] curr = q.poll();
			if(curr[0] == y) {
				System.out.println(curr[1]);
				return;
			}
			for(int i=1;i<=n;i++) {
				if(connect[curr[0]][i] && !visit[i]) {
					q.offer(new int[] {i,curr[1]+1});
					visit[i] = true;
				}
			}
		}
		System.out.println(-1);
	}
}