백준 2644 촌수계산 자바(java)

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

2644번: 촌수계산

 

풀이방법

BFS를 이용하였다. 두 사람 A, B 의 촌수가 3촌이라고 하면 A의 일촌 C -> C의 일촌 D -> D의 일촌 B 이런 식으로 일촌으로 이어진 사람들을 차례대로 따라가서 알아낼 수 있다. 구체적인 풀이는 아래와 같다. 

 

1. map 에 key : 사람 번호, value: 일촌 리스트로 하여 저장한다.

   (주의할 것은 부모, 자식 입력 시 양방향 일촌이기 때문에 양쪽 다 리스트에 삽입해주어야 한다.)

2. 탐색 시작 전 큐에 배열 [A, 0] 을 삽입하고 A 방문 체크한다. [사람 번호, A와의 촌수] 를 의미한다.

3. 큐에서 하나 꺼낸다. 꺼낸 대상의 일촌 리스트를 순회하여 아직 방문하지 않은 사람에 대해

    [사람 번호, 현재까지의 촌수+1] 을 큐에 삽입한다.

4. 2, 3번을 계속 반복한다.

5. 큐에서 꺼낸 사람이 B 가 나올 경우 정답을 현재 촌수로 갱신하고 탐색을 종료한다. 

 

코드

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

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] line = br.readLine().split(" ");
        int a = Integer.parseInt(line[0]);
        int b = Integer.parseInt(line[1]);
        int m = Integer.parseInt(br.readLine());
        Map<Integer, List<Integer>> map = new HashMap<>();
        for(int i=1; i<=n ;i++) {
            map.put(i, new ArrayList<>());
        }

        for(int i=0; i<m; i++) {
            line = br.readLine().split(" ");
            int x = Integer.parseInt(line[0]);
            int y = Integer.parseInt(line[1]);
            // x와 y는 양방향 일촌 관계
            map.get(x).add(y);
            map.get(y).add(x);
        }

        int answer = -1;
        Queue<int[]> q = new LinkedList<>();
        boolean[] visited = new boolean[n+1];
        q.add(new int[]{a, 0}); // 사람의 번호, 촌 수
        visited[a] = true;

        while(!q.isEmpty()) {
            int[] arr = q.poll();
            int person = arr[0];
            int degree = arr[1]; // 촌 수
            if(person == b) {
                answer = degree;
                break;
            }
            // 일촌 관계인 사람들 탐색
            for(Integer num : map.get(person)) {
                // 방문하지 않은 사람이면 큐에 삽입
                if(!visited[num]) {
                    visited[num] = true;
                    q.add(new int[]{num, degree + 1});
                }
            }
        }
        System.out.println(answer);
    }
}