[BJ2644] 촌수계산

 백준 - 촌수계산 

문제 링크

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

2644번: 촌수계산

 

문제 입출력

9
7 3
7
1 2
1 3
2 7
2 8
2 9
4 5
4 6

3

 

문제 풀이

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

/*
 * 주의
 * - 두사람의 친척관계가 전혀없을 때는 -1 출력 
 * */


// N: 사람 수
// A, B: 구해야하는 
public class Main {
	static int ans, N, A, B, M;
	static int[][] matrix = new int[101][101];

	static Queue<Integer> q = new ArrayDeque<>();


	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());

		StringTokenizer st = new StringTokenizer(br.readLine());
		A = Integer.parseInt(st.nextToken());
		B = Integer.parseInt(st.nextToken());

		M = Integer.parseInt(br.readLine());
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			matrix[from][to] = 1;
			matrix[to][from] = 1;
		}

		// 초기화
		ans = -1;

		// 탐색
		bfs(A);

		// 출력
		System.out.println(ans);

	} // end main


	private static void bfs(int s) {
		q.offer(s);
		matrix[s][0] = 1;

		int dep = 0;
		while (!q.isEmpty()) {
			int size = q.size();

			for (int i = 0; i < size; i++) {
				int cur = q.poll();
				// System.out.println(cur);

				if (cur == B) {
					ans = dep;
					return;
				}

				for (int j = 1; j <= 100; j++) {
					if (matrix[j][0] == 1) continue;
					if (matrix[cur][j] == 0) continue;

					q.offer(j);
					matrix[j][0] = 1;
				}
			}

			dep++;
		}
	} // end bfs

}

• dfs 를 이용해 depth 를 셉니다.
• 따라서 q의 size 만큼 돌아줍니다.
• 만약 촌수를 계산해야하는 노드까지 가면 멈춥니다.

 

 

 

 

 

 

 

 

 

# 백준 촌수계산 bfs

---