b2644. 촌수계산

 

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

 

 

 

👨‍👩‍👧 자바로 푸는 촌수 계산 (백준 2644)

 

---

 

📌 문제 개요

 

• 사람 수 n과 두 사람 x, y가 주어짐
• l개의 부모-자식 관계도 입력됨
• 두 사람 간의 촌수를 계산하는 문제

 

 

촌수란?

 

• 부모와 자식은 1촌, 형제는 2촌
• 부모-자식 관계만 주어지므로 그래프는 무방향 연결 그래프

 

---

 

💡 예제 입력

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

→ 7과 3의 관계는 다음과 같음:

7 → 2 → 1 → 3 → 총 3촌

 

 

예제 출력

3

 

---

 

🧠 알고리즘 접근 방식

 

• 각 사람을 정점으로 생각하고 양방향 그래프 구성
• DFS로 x부터 시작해서 y에 도달하는 경우를 탐색
• 탐색 중 방문한 깊이 cnt를 통해 촌수를 구함

 

---

 

🔁 전체 코드

import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    static List<Integer>[] relation;
    static boolean[] checked;
    static int res = -1;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        relation = new ArrayList[n+1];
        checked = new boolean[n+1];
        for(int i = 1; i <= n; i++) {
            relation[i] = new ArrayList<>();
        }

        StringTokenizer st = new StringTokenizer(br.readLine());
        int x = Integer.parseInt(st.nextToken());
        int y = Integer.parseInt(st.nextToken());

        int l = Integer.parseInt(br.readLine());
        for(int i = 0; i < l; i++) {
            st = new StringTokenizer(br.readLine());
            int p = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            relation[p].add(c);
            relation[c].add(p);
        }

        dfs(x, y, 0);
        System.out.println(res);
    }

    static void dfs(int start, int end, int cnt) {
        if(start == end) {
            res = cnt;
            return;
        }

        checked[start] = true;
        for(int next : relation[start]) {
            if(!checked[next]) {
                dfs(next, end, cnt+1);
            }
        }
    }
}

 

---

 

🔍 코드 해설

구문	설명
relation[p].add(c); relation[c].add(p);	무방향 그래프 구성
dfs(x, y, 0)	DFS로 x부터 y까지 촌수 탐색
if(start == end)	목적지에 도달했을 때 현재 촌수를 저장
checked[start]	방문 여부 체크로 무한 재귀 방지

 

---

 

✅ 핵심 포인트 요약

 

• 트리처럼 보이지만 실제로는 양방향 그래프 탐색
• DFS를 통해 거리(=촌수)를 누적하며 탐색
• 두 노드가 연결되지 않았다면 res는 -1로 유지됨