[백준 2644] - 촌수계산

문제

• 우리 나라는 가족 혹은 친척들 사이의 관계를 촌수라는 단위로 표현하는 독특한 문화를 가지고 있다.
• 이러한 촌수는 다음과 같은 방식으로 계산된다.
• 기본적으로 부모와 자식 사이를 1촌으로 정의하고 이로부터 사람들 간의 촌수를 계산한다.
  • 예를 들면 나와 아버지, 아버지와 할아버지는 각각 1촌으로 나와 할아버지는 2촌이 되고, 아버지 형제들과 할아버지는 1촌, 나와 아버지 형제들과는 3촌이 된다.
• 여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성하시오.

입력

• 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다.
• 입력 파일 내용은 다음과 같다.
  • 첫째 줄에는 전체 사람의 수 n이 주어진다.
  • 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진다.
  • 그리고 셋째 줄에는 부모 자식들 간의 관계의 개수 m이 주어진다.
  • 넷째 줄부터는 부모 자식간의 관계를 나타내는 두 번호 x, y가 각 줄에 나온다.
    • 이때 앞에 나오는 번호 x는 뒤에 나오는 정수 y의 부모 번호를 나타낸다.
• 각 사람의 부모는 최대 한 명만 주어진다.

출력

• 입력에서 요구한 두 사람의 촌수를 나타내는 정수를 출력한다.
• 어떤 경우에는 두 사람의 친척 관계가 전혀 없어 촌수를 계산할 수 없을 경우가 있는 데, 이때에는 -1을 출력해야 한다.

 

솔루션

• BFS를 사용하여 푸는 문제이다.
• x 또는 y를 출발점으로 잡은 후에 다음 정점으로 이동하면서 조건을 확인한다. 여기서는 x를 출발점으로 잡는다.
  • 현재와 다음 정점이 연결되어 있는지
  • 다음 정점을 아직 방문 하지 않았는지
• 위 두 조건을 모두 만족한다면 현재 정점의 촌수 + 1을 하여 다음 정점 촌수를 초기화해준다.
• 모든 정점을 방문하고 만약 depth[y] == 0이면 촌수를 계산할 수 없는 것이므로 -1을 출력하며, 그 이외는 촌수 값을 그대로 출력해주면 된다.

 

Code

• 전체 코드 : Solution2644

public class Solution_2644 {
    static int[][] graph;
    static boolean[] visited;
    static int[] depth;
    static int n;
 
    public static int DegreeOfKinship(int x, int y) { // 촌수 계산 x = 부모, y = 자식
        Queue<Integer> queue = new LinkedList<>();
        int answer = 1;
 
        visited[x] = true;
        queue.add(x);
 
        while (!queue.isEmpty()) {
            int cur = queue.poll();
 
            for (int i = 1; i <= n; i++) {              // 두 사람이 1촌으로 연결되어 있고
                if(graph[cur][i] == 1 && !visited[i]) { // 아직 방문하지 않았다면
                    depth[i] = depth[cur] + 1;          // 다음 (i) 촌수는 현재 (cur) 촌수 + 1을 해준다.
                    visited[i] = true;
                    queue.add(i);
                }
            }
        }
        
        return depth[y] == 0 ? -1 : depth[y]; // depth[y] == 0이라는 것은 연결되어 있지 않다는 것이므로
   }                                          // -1을 출력하고 이외의 경우면 연결되어 있으므로 그대로 출력한다.
}

 

결과

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