[Java] 백준 2644번: 촌수계산

문제

💡 일단 생각하기!

백준 2606번 바이러스 문제처럼 BFS로 풀이했다가 DFS로 수정했다 😅
부모 자식 관계임이 중요하므로 x가 y의 부모일때만 배열에 1로 저장해주고 count가 0일 경우 친척 관계가 없는 것이므로 -1을 출력한다

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

/**
 * 백준 2644번 촌수계산
 * 메모리 : 11568KB 시간 : 68ms
 * 
 * 아이디어
 * - 어제 풀었던 바이러스 문제처럼 BFS로 풀이하는 문제인줄 알았는데 촌수를 계산해야 하는 사람의 번호가 주어지기 때문에 DFS로 풀이해야 한다
 * - 바이러스 문제와는 다르게 x가 y의 부모일때만 배열에 표시를 해줌
 * - count가 0이면 친척 관계가 없는 것이므로 -1 출력
 */

public class BJ_2644_촌수계산_김유나 {
	static boolean isVisited[];
	static int count = 0, answer, n, m, arr[][], b;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		n = Integer.parseInt(br.readLine()); // 전체 사람 수
		
		st = new StringTokenizer(br.readLine());
		int a = Integer.parseInt(st.nextToken()); // 계산할 첫번재 사람
		b = Integer.parseInt(st.nextToken()); // 계산할 두번째 사람
		
		m = Integer.parseInt(br.readLine()); // 부모 자식들 간의 관계 수
		
		arr = new int[n + 1][n + 1];
		isVisited = new boolean[n + 1];
		
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			
			arr[x][y] = 1; // x가 y의 부모임을 표시
		}
		
		isVisited[a] = true;
		dfs(a, 0);
		
		if (answer == 0) System.out.println(-1);
		else System.out.println(answer);
	}
	
	static void dfs(int num, int count) {
		if (num == b) {
			answer = count;
			return;
		}
		
		for (int i = 1; i <= n; i++) {
			if ((arr[num][i] == 1 || arr[i][num] == 1) && !isVisited[i]) {
				isVisited[i] = true;
				dfs(i, count + 1);
				isVisited[i] = false;
			}
		}
	}
}