[알고리즘] 백준 2644 촌수계산 -bfs-

www.acmicpc.net/problem/2644

2644번: 촌수계산

 

 

간단한 BFS를 사용하는 문제였습니다. 

 

풀이는 다음과 같습니다.

1. 찾아햘 관계 num1, num2 가 있다.

2. num1을 시작으로 BFS 탐색을 하여 가족 관계를 찾기 시작한다.

3. 가족관계인 번호를 찾으면 촌수를 1 증가시키고 계속해서 2번을 반복한다.

4. 2~3을 num2를 찾을때까지 반복한다. 

 

 

[Java]

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Main {
    static int n;
    static int[][] map;
    static boolean[] isVisited;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        isVisited = new boolean[n + 1];
        map = new int[n + 1][n + 1];
        //촌수를 계산해야하는 서로 다른 두 사람의 번호
        int num1 = sc.nextInt();
        int num2 = sc.nextInt();
        int m = sc.nextInt(); //부모자식관계 수
        for (int i = 0; i < m; i++) {
            int x = sc.nextInt(); //부모
            int y = sc.nextInt(); //자식
            map[x][y] = 1;
            map[y][x] = 1;
        }
        bfs(num1, num2);
    }

    private static void bfs(int start, int end) {
        boolean isFind = false;
        Queue<Person> queue = new LinkedList<>();
        queue.offer(new Person(start, 0));
        isVisited[start] = true;
        while (!queue.isEmpty()) {
            Person person = queue.poll();
            int start2 = person.x;
            if (start2 == end) { //찾아야할 관계 찾은 경우
                isFind = true;
                System.out.println(person.cnt);
                break;
            }
            for (int i = 1; i <= n; i++) { //아직 방문 안하고 관계가 있는 촌수 탐색
                if (!isVisited[i] && map[start2][i] == 1) {
                    isVisited[i] = true;
                    queue.offer(new Person(i, person.cnt + 1));
                }
            }
        }
        if (!isFind) System.out.println(-1); //촌수관계 X
    }

    private static class Person {
        int x; //번호
        int cnt; //촌수

        public Person(int x, int cnt) {
            this.x = x;
            this.cnt = cnt;
        }
    }
}

 

 

댓글과 공감은 큰 힘이 됩니다. !!