백준_2644번_촌수계산_자바

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

2644번: 촌수계산

백준_2644번_촌수계산 문제는 bfs,dfs로 모두 풀 수 있는 그래프 문제이며,

개인적으로 더 편한 bfs로 풀이하였습니다.

 

 

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

public class Main {

    static int start,end,n;
    static int[][] graph;
    static int[] dist;

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());
        dist = new int[n+1];
        graph = new int[n+1][n+1];

        StringTokenizer st = new StringTokenizer(br.readLine());
        start = Integer.parseInt(st.nextToken());
        end = Integer.parseInt(st.nextToken());

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

        for (int i = 0; i < line; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            graph[a][b] = graph[b][a] = 1;
        }

        bfs(start);

        System.out.println(dist[end] == 0? -1:dist[end]);

    }

    private static void bfs(int x) {
        Queue<Integer> q = new LinkedList<>();
        q.add(x);

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


            for (int i = 0; i <=n; i++) {
                if(graph[nx][i] == 1 && dist[i]==0){
                    q.add(i);
                    dist[i] = dist[nx]+1;
                }
            }
        }
    }
}