백준 - 2644

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

class Main {
    static int N;
    static List<Integer>[] graph;
    static int ch;
    static int[] target;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        String[] a = br.readLine().split(" ");
        int par = Integer.parseInt(a[0]);
        ch = Integer.parseInt(a[1]);

        graph = new ArrayList[N+1];
        for(int i = 1; i <= N; i++){
            graph[i] = new ArrayList<>();
        }
        int l = Integer.parseInt(br.readLine());
        for(int i = 0; i < l; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int parent = Integer.parseInt(st.nextToken());
            int child = Integer.parseInt(st.nextToken());

            graph[parent].add(child);
            graph[child].add(parent);
        }
        target = new int[N+1];
        System.out.println(bfs(par));
    }
    static int bfs(int p){
        boolean[] visited = new boolean[N+1];
        Queue<Integer> q = new ArrayDeque<>();
        visited[p] = true;
        q.offer(p);

        while(!q.isEmpty()){
            int prev = q.poll();
            for(int next : graph[prev]){
                if(!visited[next]){
                    visited[next] = true;
                    q.offer(next);
                    target[next] = target[prev] + 1;
                    if(next == ch) return target[next];
                }
            }
        }
        return -1;
    }
}

풀이과정 및 리뷰

1. 촌수 계산 ⇒ 시작점에서 도착점까지 도달하는 최단거리가 촌수이므로 bfs로 최단거리 찾기 시작
2. 노드 연결관계 저장할 List<Integer>[] graph , 방문여부 저장할 boolean[] visited, 타켓(시작점)에서 목적지까지 도달하는데 걸리는 거리 저장할 int[] target 배열 선언
3. bfs선언
   • 일단 출발지 방문체크 후 큐에 넣음
   • 큐가 빌 때까지 반복
     • 이전 노드와 연결된 지점들 중 방문하지 않은 노드 탐색
     • 방문하지 않았을 경우 방문체크후 큐에 삽입
     • target[next] 인덱스에 이전 prev 인덱스 + 1값 저장해 최단거리 계산
     • sysout에서 한번에 존재/존재X시의 값 리턴 위해, next == ch(목적지) 조건에 걸리는 경우 target[next]를 리턴하도록 코드 추가