[백준] 2644 촌수계산 java 풀이

1. 문제 설명

2. 접근 방식

1. 인접 리스트로 그래프를 구현한다. (인접 리스트 구현 방법: 링크)
2. DFS로 시작정점에서 목표 정점을 찾을 때까지 재귀한다.
3. 목표 정점을 찾았을 때 재귀의 Depth가 바로, 답이다. DFS를 돌아도 값을 찾지 못하는 경우에는 -1을 출력한다.

3. 코드 분석

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

public class Main {
    // 각각 정점 개수, 확인해야할 노두 2개, 간선 개수
    static int N, me, cousin, M;
    static boolean foundAns = false;
    static ArrayList<Integer> [] lists;
    static boolean [] isVisited;
    public static void main(String[] args) throws IOException {
        // 입력 받기
        BufferedReader br   = new BufferedReader(new InputStreamReader(System.in));
        N       = Integer.parseInt(br.readLine());
        StringTokenizer st  = new StringTokenizer(br.readLine());
        me      = Integer.parseInt(st.nextToken());
        cousin  = Integer.parseInt(st.nextToken());
        M       = Integer.parseInt(br.readLine());

        lists = new ArrayList[N+1];
        isVisited = new boolean[N+1]; isVisited[me] = true;
        for (int i = 1; i <=N ; i++) {
            lists[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());
            lists[start].add(end);
            lists[end].add(start);
        }
        dfs(0, me);
        if (!foundAns) {
            System.out.println(-1);
        }
    }

    public static void dfs(int depth, int now) {
        // 1. 기저 조건
        if(now == cousin) {
            System.out.println(depth);
            foundAns = true;
            return;
        }
        // 2. 계산 조건
        for (int i = 0; i < lists[now].size(); i++) {
            int next = lists[now].get(i);
            if(!isVisited[next]) {
                isVisited[next] = true;
                dfs(depth+1, next);
                if(foundAns) return;
                isVisited[next] = false;
            }
        }
    }
}

4. 성장 하기

#1 문제를 다 읽지 않고 풀어서, 못 찾으면 -1 출력을 구현 안했다. 그거 때문에 헤맸다.

#2 DFS 돌 때, 시작 정점을 방문 체크 안해서 작동하지 않는 예시가 몇 개 있었다. 그거 때문에도 헤맸다.