[백준/java] 2644번: 촌수계산 - 인접행렬을 이용한 DFS

2644번: 촌수계산

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

처음 9는 전체 사람의 수 n이고,

두번째 줄에 주어지는 수로 촌수를 구하면 된다.

 

즉, 7번과 3번의 촌수를 구하면 된다.

 

세번째 줄의 7은 부모와 자식의 관계를 나타낸다.

 

1번은 2번의 부모

1번은 3번의 부모

 

백준 2644번 촌수계산

 

인접행렬로 표현하면 위와 같을 것이다.

 

이제 7번에서 출발하여 3번으로 가는 촌수를 찾아보면

 

7과 관계된 촌수를 찾기위해, 7행부터 보면

 

7행 2열에 1이 있는 것을 확인할 수 있다.

 

백준 2644번 촌수계산

7의 아버지는 2이기 때문에 거쳐가는 의미에서 cnt 1을 증가시킨다.

 

다음은 2행으로 간다.

 

2행에서는 직계가족이 1, 7, 8, 9가 존재한다.

 

이중에서 무엇이 아버지인지 알 수 있는 방법은 본인의 값보다 더 작은 수가 더 손윗사람이 된다.

 

하지만 문제를 푸는데 있어서 손윗사람을 알 필요는 없다.

 

어떤 수를 통해서 촌수를 잘 찾아가느냐가 관건이다.

 

백준 2644번 촌수계산

2행에서 1행으로 이동하기 전에 cnt를 1 증가시켜서 2로 만들어준다.

 

백준 2644번 촌수계산

1행으로 가서 직계가족이 2, 3이 존재한다.

 

우리가 원하는 정답을 찾았다. 3이 있다.

 

그러나 아직 1행이기 때문에 정확한 촌수 카운트를 위해 cnt에 1을 더해주면 정답을 구할 수 있다.

 

package dfsAndBfs;

/**
 *  https://www.acmicpc.net/problem/2644
 *  백준 2644번 촌수계산
 */

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

public class P2644_CalculateDegreeOfKinship {
	static int[][] family;
	static boolean[] check;
	static int answer, n, m;
	static boolean find;
	
	public static void dfs(int man1, int man2, int cnt) {
		check[man1] = true; 
		
		if(man1 == man2) {
			find = true;
			answer = cnt;
			return;
		}
		
		for (int i = 0; i < n; i++) {
			if(!check[i] && family[man1][i] == 1) {
				check[i] = true;
				dfs(i, man2, cnt+1);
				check[i] = false;
			}
		}
		
	}
	
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = stoi(br.readLine());
		
		family = new int[n][n];
		check = new boolean[n];
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		int man1 = stoi(st.nextToken())-1, man2 = stoi(st.nextToken())-1;
		
		m = stoi(br.readLine());
		
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int first = stoi(st.nextToken()) - 1;
			int second = stoi(st.nextToken()) - 1;
			
			family[first][second] = 1;
			family[second][first] = 1;
		}
		
		dfs(man1, man2, 0);
		
		if(!find) answer = -1;
		System.out.println(answer);
	}
	
	public static int stoi(String str) {
		return Integer.parseInt(str);
	}
}