[백준 java] 2644-촌수계산

 

2644번: 촌수계산

 

이전문제 2606 바이러스와 다른점은 해당 문제의 예제처럼

9
7 3
7
1 2
1 3
2 7
2 8
2 9
4 5
4 6

7 과 3의 촌수를 구하는 문제이므로 7-2 2-1 1-3 으로 3촌의 관계가 된다

아래 코드에서는 큐에 넣을때 카운터를 +1 해줘서 3이 들어갈때도 count+1이 된다 

따라서 최종값 res에 -1을 해주면 촌수관계가 된다

 

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

public class B2644 {
    static int N,M,x,y;
    static int res=0;
    static int[][] Graph;
    static boolean[] visited;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        x = sc.nextInt();
        y = sc.nextInt();
        M = sc.nextInt();
        Graph = new int[N+1][N+1];
        visited = new boolean[N+1];
        for(int i = 0; i<M; i++){
            int a = sc.nextInt();
            int b = sc.nextInt();

            Graph[a][b] = Graph[b][a] = 1;
        }
        bfs();
    }


    public static void bfs(){
        Queue<Node> queue = new LinkedList<>();
        visited[x]=true;
        queue.add(new Node(x,1));
        boolean match = false;

        while(!queue.isEmpty()){
            Node temp = queue.remove();
            if(temp.num == y){
                if(res==0) {
                    res = temp.count;
                }else{
                    if(res>temp.count) res = temp.count;
                }
                match = true;
            }

            for(int i=1; i<N+1; i++){
                if(!visited[i] && (Graph[temp.num][i] == 1)){
                    visited[i] = true;
                    queue.add(new Node(i , temp.count+1 ));
                }
            }
        }
        if(!match) System.out.println(-1);
        if(match) System.out.println(res-1);
    }

    static class Node{
        int num ,count;
        Node(int n, int c){
            num = n;
            count = c;
        }
    }
}