[백준 JAVA] 2644 : 촌수계산

[백준 2644] 촌수계산 : https://www.acmicpc.net/problem/2644

2644번: 촌수계산

 

---

문제 조건 정리

 

1. 기본적으로 부모와 자식 사이를 1촌으로 정의하고 이로부터 사람들 간의 촌수를 계산한다.
2. [나, 아버지] -> 1촌, [아버지, 할아버지]-> 1촌
   [나, 할아버지] -> 2촌 [아버지 형제, 할아버지] -> 1촌
   [나, 아버지 형제] -> 3촌
3. 여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성하시오.

---

입력

 

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

---

문제를 풀기 전

 

1. 부모 자식들 간의 관계는 양방향으로 설정해야겠다고 생각함!

---

코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bufferedReader.readLine());
        List<List<Integer>> adjList = new ArrayList<>();

        for (int i = 0; i <= n; i++) {
            // 1 ~ n 번의 사람들과 1촌인 사람을 정리하기 위한 리스트 초기화
            // 0 번도 초기화 해야함
            adjList.add(new ArrayList<>());
        }

        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine(), " ");

        // start부터 end까지 몇 촌인가? 를 구하는 문제
        int start = Integer.parseInt(stringTokenizer.nextToken());
        int end = Integer.parseInt(stringTokenizer.nextToken());
		
        // 부모 자식들 간의 관계의 개수 m
        int m = Integer.parseInt(bufferedReader.readLine());

        for (int i = 0; i < m; i++) {
            stringTokenizer = new StringTokenizer(bufferedReader.readLine(), " ");
            // [first, second] -> 1촌 
            int first = Integer.parseInt(stringTokenizer.nextToken());
            int second = Integer.parseInt(stringTokenizer.nextToken());
			
            // [first, second] -> 1촌 
            // [second, first] -> 1촌 
            adjList.get(first).add(second);
            adjList.get(second).add(first);
        }
		
        // bfs를 위한 큐
        // 재방문을 검사하는 visited 배열
        // 각 노드까지의 거리를 저장할 distance 배열
        Queue<Integer> queue = new ArrayDeque<>();
        boolean[] visited = new boolean[n + 1];
        int[] distance = new int[n + 1];

        // [start, end]를 구하기 위해서 start를 넣고 시작
        queue.offer(start); 
        visited[start] = true;

        while (!queue.isEmpty()) {
            int current = queue.poll();

            // 현재 요소가 도착 지점일 경우 거리 출력하고 끝냄
            if (current == end) {
                System.out.println(distance[end]);
                return;
            }

            // 현재 요소와 인접한 요소들을 가져옴
            List<Integer> adj = adjList.get(current);

            // 가져온 요소들을 처리
            for (Integer a : adj) {
                // 방문한 적이 없다면
                if (!visited[a]) {
                    // 방문 표시
                    visited[a] = true;
                    // 큐에 추가
                    queue.offer(a);
                    // 큐에 추가된 요소는 (현재 촌수 + 1)로 저장
                    distance[a] = distance[current] + 1;
                }
            }
        }

        // 큐가 비었음에도 end에 도달하지 못했다면 조건대로 -1 출력
        System.out.println(-1);
    }
}

 

---

문제를 풀고 난 후

 

원래 bfs문제를 해결 할 때, 현재 요소의 깊이를 알아내기 위해서 depth를 포함하는 class를 선언하고 이를 큐에서 사용했었음!

이번에는 distance 배열로 해결해보니 이것도 괜찮다고 생각했음!