[백준] 2644번 촌수계산

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

2644번: 촌수계산

문제풀이: 촌수를 계산하기 위하여 그래프 이용, 번호로 된 사람이 정점, 간선의 수가 촌수의 수가 됩니다. 그래프를 인접행렬 map으로 나타내줍니다. check 배열은 촌수의 수를 구하기 위한 배열입니다. bfs를 활용합니다. 이때 주의할 점은 촌수를 계산할 수 없을 때 -1을 출력합니다.

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	static int n = 0, m = 0, start = 0, end = 0;
	static int[][] map;
	static boolean[] visited;
	static int[] check;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();//9
		start = sc.nextInt();//7
		end = sc.nextInt();//3
		m = sc.nextInt();//7
		
		map = new int[n+1][n+1];
		visited = new boolean[n+1];
		check = new int[n+1];
		
		for (int i = 0; i < m; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			map[a][b] = 1;
			map[b][a] = 1;
		}

		
		bfs(start);
		
	}
	public static void bfs(int start) {
		Queue<Integer> queue = new LinkedList();
		queue.add(start);
		visited[start] = true;
		while(!queue.isEmpty()) {
			
			int x = queue.poll();
			for (int i = 0; i < map.length; i++) {
				if(map[x][i] == 1 && !visited[i]) {
					queue.add(i);
					visited[i] = true;
					check[i] = check[x]+1;
				}
			}
		}
		
		System.out.println(check[end]==0?-1:check[end]);
	}
}