[알고리즘/백준] 2644번 : 촌수계산(Java)

문제	2644번 : 촌수계산
문제링크	https://www.acmicpc.net/problem/2644
난이도	S2
언어	Java
분류	그래프이론, 그래프탐색, 너비우선탐색, 깊이우선탐색

 

 

📌 최종 정답 코드

import java.io.*;
import java.util.*;

public class Main {
    static int n; // 전체 사람의 수
    static ArrayList<Integer>[] graph; // 가족 관계를 저장할 인접 리스트
    static boolean[] visited; // 방문 여부를 체크할 배열
    static int result = -1; // 촌수를 저장할 변수 (기본값은 -1)

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 전체 사람의 수 입력
        n = Integer.parseInt(br.readLine());
        // 인접 리스트 초기화
        graph = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }

        // 촌수를 계산할 두 사람 입력
        StringTokenizer st = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(st.nextToken()); // 시작 사람
        int end = Integer.parseInt(st.nextToken());   // 목표 사람

        // 가족 관계의 수 입력
        int m = Integer.parseInt(br.readLine());

        // 가족 관계를 인접 리스트에 저장
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            graph[x].add(y);
            graph[y].add(x); // 양방향 관계
        }

        // 방문 배열 초기화
        visited = new boolean[n + 1];

        // DFS를 통해 촌수 계산
        dfs(start, end, 0);

        // 결과 출력
        bw.write(String.valueOf(result));
        bw.newLine();
        bw.flush();
        bw.close();
        br.close();
    }

    // DFS 메서드: 현재 노드에서 목표 노드까지의 촌수를 계산
    static void dfs(int current, int target, int count) {
        visited[current] = true; // 현재 노드 방문 처리

        if (current == target) {
            result = count; // 목표 노드에 도달하면 촌수 저장
            return;
        }

        // 현재 노드와 연결된 노드들을 순회
        for (int neighbor : graph[current]) {
            if (!visited[neighbor]) {
                dfs(neighbor, target, count + 1); // 재귀 호출로 깊이 탐색
            }
        }
    }
}

📌 구해야 하는 정답

- 입력에서 요구한 두 사람의 촌수를 나타내는 정수를 출력

- 어떤 경우에는 두 사람의 친척 관계가 전혀 없어 촌수를 계산할 수 없을 때는 -1을 출력

📌 코드 설계하기

1. 입력 처리

 

- 전체 사람 수 n

- 촌수 계산 대상 두 사람 start, end

- 가족 관계 개수 m, 이후 m개의 관계 (x, y)

 

2. 그래프 구성

- ArrayList<Integer>[] graph로 인접 리스트 구성 (양방향 연결)

 

3. DFS 탐색

- 방문 여부 체크 (visited[])

- DFS로 start에서 end까지 촌수 누적

- 목표에 도달하면 촌수(result) 저장 후 종료

 

3. 출력

- 결과를 BufferedWriter로 출력