[백준] 2644 촌수계산

www.acmicpc.net/problem/2644

2644번: 촌수계산

2020-11-09

---

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

public class Main2644 {
	public static int N, M, num1, num2, count, arr[][];
	public static boolean vtd[], flag;
	public static Queue<Integer> q;
	
	public static void solve() {
		loop:while(!q.isEmpty()) {
			int size = q.size();
			while(size > 0) {
				int x = q.poll();
				
				for(int i = 0; i < N; i++) {
					if((arr[x][i] == 1 || arr[i][x] == 1) && !vtd[i]) {
						if(i == num2) {
							count++;
							flag = true;
							break loop;
						}
						q.add(i);
						vtd[i] = true;
					}
				}		
				size--;
			}
			count++;
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		num1 = sc.nextInt()-1;
		num2 = sc.nextInt()-1;
		
		M = sc.nextInt();
		count = 0;
		arr = new int[N][N];
		vtd = new boolean[N];
		flag = false;
		for(int i = 0; i < M; i++) {
			int x = sc.nextInt();
			int y = sc.nextInt();
			arr[x-1][y-1] = 1;
		}
		
		q = new LinkedList<Integer>();
		q.add(num1);
		vtd[num1] = true;
		solve();
		if(flag) System.out.println(count);
		else System.out.println("-1");
	}
}

1. 촌수를 계산해야 할 두 사람의 번호 중 하나를 선택하여 queue에 넣는다.

 

2. 선택한 사람과 연결된 모든 번호를 queue에 추가 할 것이기 때문에, 초기에 queue의 사이즈를 계산하여 번호를 추가해도 초기값만큼만 돌 수 있도록 한다.

 

3.  방문한 적이 없으며, 촌수가 연결된 경우 queue에 넣는다. 이 때, 계산해야 할 다른 번호를 찾게 되면 멈춘다.

 

4. 선택한 사람과 연결된 모든 관계를 체크해봐도 계산해야 할 다른 번호를 찾지 못하면 -1을 출력한다.