[BOJ/BFS] 백준 2644 - 촌수계산 (Java)

2644 - 촌수계산

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

문제

부모와 자식 사이를 1촌으로 정의하고 이로부터 사람들 간의 촌수를 계산
ex, 나와 아버지, 아버지와 할아버지는 각각 1촌으로 나와 할아버지는 2촌
/ 아버지 형제들과 할아버지는 1촌, 나와 아버지 형제들과는 3촌

=> 여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램?

입력
사람들은 1, 2, 3, ..., n (1 <= n <= 100)의 연속된 번호로 각각 표시
첫째 줄: 전체 사람의 수 n
둘째 줄: 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어짐
셋째 줄: 부모 자식들 간의 관계 개수 m
넷째 줄부터는 부모 자식간의 관계를 나타내는 두 번호 x, y (x는 y의 부모 번호)
각 사람의 부모는 최대 한 명만 주어짐
출력
요구한 두 사람의 촌수를 나타내는 정수 출력
어떤 경우에는 두 사람의 친척 관계 X -> 촌수 계산 X => -1 출력

---

풀이

• `ArrayList<Integer>[] graph`: 관계 저장 그래프 (무방향 인접 리스트)
  
  • 인접 리스트 초기화

graph = new ArrayList[n + 1];
for (int i = 1; i <= n; i++) graph[i] = new ArrayList<>();

while (m-- > 0) {
    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);
}

• `int[] dist`: 각 노드까지의 거리(촌수) 저장

 

BFS

• 시작 노드(start) -> 큐에 넣고 방문 처리, 촌수: 0
  • `start == end`: 목표 노드에 도착 => 최소 촌수 거리 출력하고 종료
• 인접 노드 중 방문 X 노드 -> 큐에 넣고 거리 + 1
• `while`문 끝날 때까지 도착 X -> 연결된 경로 X => -1 출력

static void bfs(int start, int end) {
    Queue<Integer> q = new LinkedList<>();
    q.offer(start);
    visited[start] = true;
    dist[start] = 0;

    while (!q.isEmpty()) {
        int cur = q.poll();

        if (cur == end) {
            System.out.println(dist[cur]);
            return;
        }

        for (int next : graph[cur]) {
            if (!visited[next]) {
                visited[next] = true;
                dist[next] = dist[cur] + 1;
                q.offer(next);
            }
        }
    }

    System.out.println(-1);
}

---

코드

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

// 촌수계산
public class boj_2644 {
    static int n;
    static ArrayList<Integer>[] graph;
    static boolean[] visited;
    static int[] dist;

    static void bfs(int start, int end) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(start);
        visited[start] = true;
        dist[start] = 0;

        while (!q.isEmpty()) {
            int cur = q.poll();

            if (cur == end) {
                System.out.println(dist[cur]);
                return;
            }

            for (int next : graph[cur]) {
                if (!visited[next]) {
                    visited[next] = true;
                    dist[next] = dist[cur] + 1;
                    q.offer(next);
                }
            }
        }

        System.out.println(-1);
    }

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

        n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());

        int m = Integer.parseInt(br.readLine());

        graph = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) graph[i] = new ArrayList<>();

        while (m-- > 0) {
            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];
        dist = new int[n + 1];

        bfs(a, b);
    }
}