백준 촌수계산 2644 java

문제링크

문제 접근

• bfs로 target1 -> target2 몇 촌 관계인지 파악
• 각 사람마다 리스트 생성

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class baek_2644 {
    static int N,M, target1,target2;
    static ArrayList<Integer> map [];
    static boolean[] visit;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        target1 = Integer.parseInt(st.nextToken());
        target2 = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());

        map = new ArrayList[N+1];
        visit = new boolean[N+1];

        for(int i=1;i<=N;i++){
            map[i] = new ArrayList<>();
        }
        for(int i=0;i<M;i++){
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            map[start].add(end);
            map[end].add(start);
        }
        bfs();
    }
    private static void bfs(){
        Queue<Integer> que = new LinkedList<>();
        que.add(target1);
        visit[target1] = true;
        int chonsu = 1;
        while(!que.isEmpty()){
            int size = que.size();
            for(int s=0;s<size;s++){
                int now = que.poll();
                for(int i=0;i<map[now].size();i++){
                    int next = map[now].get(i);
                    if(visit[next]) continue;
                    if(next == target2) {
                        System.out.println(chonsu);
                        return;
                    }
                    que.add(next);
                    visit[next] = true;
                }
            }
            chonsu++;
        }
        System.out.println(-1);
    }
}

결과

정리

• 스무스하다
• 근데 이런거 풀때 항상 먼저 bfs로 접근해서 dfs로도 풀어봐야 할 듯