백준 2644번 : 촌수계산 java

이 문제는 사람의 수를 입력받고 두 사람의 번호를 입력받아 두 사람이 몇 촌 관계인지를 확인하는 문제입니다.

이 문제를 풀기 위해서 사람들간의 촌수 관계를 인접 리스트에 저장한 후 dfs로 순회하면 됩니다.

시작점을 한 명의 번호로 두고 찾고자 하는 사람의 번호를 찾으면 return 하게 함수를 만들었습니다.

여기서 연결 리스트란 한 정점과 연결되어 있는 다른 정점들을 나타내는 방식입니다.

위의 그림과 같이 정점들이 연결되어 있다고 하겠습니다.

이 그래프를 인접 리스트로 나타내면 위와 같은 그림이 나옵니다.

임의의 정점에 어떤 정점들이 연결되어 있는지를 나타내는 방식이 인접리스트입니다.

이제 코드를 보여드리도록 하겠습니다.

---

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

public class Main {
    static int N, v2;
    static boolean[] visited;
    static List<List<Integer>> l = new ArrayList<>();

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        visited = new boolean[N+1];

        for(int i = 0; i<=N; i++)
            l.add(new ArrayList<>());

        StringTokenizer st = new StringTokenizer(br.readLine());
        int v1 = Integer.parseInt(st.nextToken());
        v2 = Integer.parseInt(st.nextToken());

        int M = Integer.parseInt(br.readLine());
        while(M-->0){
            st = new StringTokenizer(br.readLine());

            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());

            l.get(A).add(B);
            l.get(B).add(A);
        }

        int answer = dfs(v1, 0);
        System.out.println(answer);
    }

    static int dfs(int v, int cnt){
        int answer = -1;

        if(v == v2)
            return cnt;

        for(int i = 0; i<l.get(v).size(); i++){
            int nextV = l.get(v).get(i);

            if(visited[nextV])
                continue;

            visited[nextV] = true;
            answer = dfs(nextV, cnt+1);
            visited[nextV] = false;

            if(answer != -1)
                break;
        }

        return answer;
    }
}

다음과 같이 인접 리스트와 dfs를 적절히 사용하시면 문제를 쉽게 해결할 수 있습니다.