[BFS] 촌수계산

촌수계산

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

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

public class Main {

    static Scanner sc = new Scanner(System.in);

    static int N, E;
    static int startNode, endNode; //구해야 되는 두 노드
    static int[][] graph;
    static boolean[] visited;

    public static void main(String[] args) {
        N = sc.nextInt(); //사람 수
        startNode = sc.nextInt(); //시작노드
        endNode = sc.nextInt(); //끝노드
        E = sc.nextInt(); //간선 수

        graph = new int[N*N+1][N*N+1];
        visited = new boolean[N+1];

        //그래프 초기화
        int v1, v2;
        for (int i = 1; i <= E; i++) {
            v1 = sc.nextInt();
            v2 = sc.nextInt();

            graph[v1][v2] = 1;
            graph[v2][v1] = 1;
        }

        //결과출력
        System.out.println( distance(startNode, endNode) );
    }

    //입력받은 두 노드의 거리를 계산
    static int distance(int sN, int eN){

        int result = -1;
        int pos; //현재위치
        int level = 0; //촌수(시작노드에서의 거리)

        Queue<Integer> queue = new LinkedList<>();
        queue.offer(sN); //시작지점을 큐에 넣음

        //큐가 빌때까지 돈다
        while ( !queue.isEmpty() ){

//            System.out.println("========== level: " + level + " ==========");
            int qSize = queue.size();
            for(int i=1; i<=qSize; i++){

                pos = queue.poll();
                if(pos == eN){ //목표지점일때
                    return level;
                }

                for(int j=1; j<=N; j++){
                    if( graph[pos][j]==1 && visited[j]==false ){
                        queue.offer(j);
                        visited[j]=true;
//                        System.out.println(j + " ");
                    }
                }//for(j)
            }//for(i)
            level++;

        }//while

        return  result;
    }
}

[input]

9

7 3

7

1 2

1 3

2 7

2 8

2 9

4 5

4 6

[output]

3