[BOJ] 2644. 촌수계산

그래프의 BFS문제이다.

List의 배열을 이용한 간단한 그래프 BFS 문제였다. 촌수를 구하기 위해 visit배열을 -1로 초기화 시켰고 start부터 시작하여 end가 만날때까지 실행을 시켰다.

package study4;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main_bj_2644_촌수계산 {
    static int N;
    static List<Integer>[] graph;
    static int start,end;
    static int[] visit;
    
    static Queue<Integer> queue;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st= null;
        
        N=Integer.parseInt(br.readLine());
        graph=new ArrayList[N+1];
        visit=new int[N+1];
        for(int i=1;i<=N;i++) {
            graph[i]=new ArrayList<>();
            visit[i]=-1;
        }
        
        st=new StringTokenizer(br.readLine());
        start=Integer.parseInt(st.nextToken());
        end=Integer.parseInt(st.nextToken());
        
        
        int n = Integer.parseInt(br.readLine());
        for(int i=0;i<n;i++) {
            st=new StringTokenizer(br.readLine());
            int u=Integer.parseInt(st.nextToken());
            int v=Integer.parseInt(st.nextToken());
            graph[u].add(v);
            graph[v].add(u);
        }
        
        queue=new LinkedList<Integer>();
        bfs();
        
        System.out.println(visit[end]);
        
    }
    
    static void bfs() {
        visit[start]=0;
        queue.offer(start);
        
        while(!queue.isEmpty()) {
            int cur=queue.poll();
            if(cur==end)
                return;
            
            for(int next : graph[cur]) {
                if(visit[next]==-1) {
                    queue.offer(next);
                    visit[next]=visit[cur]+1;
                }
            }
        }
    }
}