ALGORITHM/BOJ
[백준] 2644 촌수계산
0298
2020. 11. 9. 20:47
2644번: 촌수계산
사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진
www.acmicpc.net
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을 출력한다.