[java 백준]실버 2/ 2644번 촌수 계산

 

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

2644번: 촌수계산

이 문제는 부모를 찾아내는거라서 유니온파인드로 풀까도 생각을 했는데 오히려 그러면 복잡해졌다. 충분히 BFS로도 해결할 수 있었다. 위에서 아래로 인접한 노드를 찾는게 아니라 아래에서 위로 인접한 노드를 찾아내는 방법도 있었다!

어차피 list[a].add(b) list[b].add(a) 를 해주니까 아래에서 위로 촌수계산을 해도 결국에 visited[i]의 횟수는 같았다.

그리고 bfs도 노드 하나를 기준으로 해줘도 된다. 인접 노드들이라는 것은 결국에 부모가 같다는 것이기 때문이다!

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
class Main {
 
 
    public static int N;
 
    public static int N1;
 
    public static int N2;
 
    public static int M;
 
    public static List<Integer>[]list;
 
    public static int visited[];
 
 
 
 
 
 
 
 
 
    public static void main(String args[]) throws NumberFormatException, IOException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        StringTokenizer st;
        N=Integer.parseInt(br.readLine());
        st=new StringTokenizer(br.readLine());
        N1=Integer.parseInt(st.nextToken());
        N2=Integer.parseInt(st.nextToken());
        M=Integer.parseInt(br.readLine());
        list= new ArrayList[N + 1];
        for(int i=0;i<N+1;i++){
            list[i]=new ArrayList<>();
        }
        visited=new int[N+1];
 
        for(int i=0;i<M;i++){
            st=new StringTokenizer(br.readLine());
            int a=Integer.parseInt(st.nextToken());
            int b=Integer.parseInt(st.nextToken());
            list[a].add(b);
            list[b].add(a);
 
 
        }
 
 
 
 
        Queue<Integer>queue=new LinkedList<>();
        queue.add(N1);
        visited[N1]+=1;
        while(!queue.isEmpty()){
            int num=queue.poll();
 
            for(int n:list[num]){
 
                if(visited[n]==0){
                    visited[n]=visited[num]+1;
                    queue.add(n);
                }
            }
        }
 
 
 
        if(visited[N2]==0){
            System.out.println(-1);
        }else{
            System.out.println(visited[N2]-1);
        }
 
 
 
 
 
 
 
 
 
 
 
 
 
 
    }
}