[백준] 문제 2644 번 : 촌수 계산 - JAVA

[링크] : https://www.acmicpc.net/problem/2644

---

💎 문제 분석 & 제약 조건

 

 

문제 분석 :

 

주어진 입력에서 촌수를 계산해야 하는 두 사람의 번호가 주어지고,

부모 자식 관계가 주어집니다. 관계를 바탕으로 두 사람 사이의 촌수를 계산한다.

관계가 없으면 -1을 출력한다.

 

 

제약 조건 : 

 

사람들은 1부터 n까지의 연속된 번호로 표시 된다.

전체 사람의 수 n은 1 ≤ n ≤ 100 이다.

입력의 첫 번째 줄에는 전체 사람의 수 n이 주어진다.

두 번째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진다.

세 번째 줄에는 부모 자식 간의 관계의 개수 m이 주어진다.

이후 m개의 줄에는 두 번호 x, y가 주어지며, x는 y의 부모 번호를 나타낸다.

각 사람의 부모는 최대 한 명만 주어진다.

 

 

---

🚀 의사 결정

 

 

 1.ArrayList를 사용한 인접 리스트 형태로 그래프를 표현하고, 노드 번호를 1부터 N까지 설정한다.

 2. BFS를 사용하여 최단 경로를 탐색한다.

 3. 방문 여부를 체크하기 위해 boolean[] visited를 사용한다.

 4. 촌수를 계산하여 출력하며, 도달하지 못하면 -1을 반환한다.

 

---

📜 소스코드(Java)

 

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

public class Main {
    static int N, M; // 총 사람의 수
    static boolean[] visited;
    static List<Integer>[] relation;

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

        // 입력
        N = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(st.nextToken()); // 촌수 계산 시작
        int target = Integer.parseInt(st.nextToken()); // 촌수 에임
        M = Integer.parseInt(br.readLine()); // 부모-자식 관계 수

        // 촌수 초기화
        relation = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            relation[i] = new ArrayList<>();
        }

        // 촌수 입력
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int parent = Integer.parseInt(st.nextToken());
            int child = Integer.parseInt(st.nextToken());
            relation[parent].add(child); // 양방향이여서 관계
            relation[child].add(parent);
        }

        // 탐색한곳 visited
        visited = new boolean[N + 1];

        // bfs 탐색
        int result = bfs(start, target);

        // 출력
        bw.write(result + "\n");
        bw.flush();
        bw.close();
        br.close();
    }

    // bfs 탐색 시작
    private static int bfs(int start, int target) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{start, 0}); // 시작 지점
        visited[start] = true; // 방문처리 ( 처음시작이니깐 )

        while (!queue.isEmpty()) {
            int[] current = queue.poll(); // 현재 위치 ( 촌수 )
            int node = current[0];
            int depth = current[1];

            if ( node == target) {
                return depth; // 시작점으로 부터 거리
            }

            //  탐색
            for(int i = 0; i < relation[node].size(); i++) {
                if (!visited[relation[node].get(i)]) {
                    queue.add(new int[]{relation[node].get(i), depth + 1});
                    visited[relation[node].get(i)] = true;
                }
            }
        }
        return -1; // 촌수 계산이 안되는 경우
    }
}

---