[백준] 2644 촌수계산(Silver.2) - DFS

문제

촌수계산

코드

• 비슷한 유형의 문제: 외판원 순회2

친척 관계를 그래프로 그려보면 아래와 같이 트리 형태가 나온다.

• 풀이 방법
  • dfs를 이용한 백트래킹 알고리즘 사용
  1. 촌수를 계산해야 하는 서로 다른 두 사람의 번호 중 하나를 출발 노드, 다른 한 노드를 목적지 노드로 설정한다.
  2. dfs로 모든 경로를 탐색한 후 목적지 노드에 도착하면 촌수(cnt)를 result에 삽입한 후 dfs를 종료한다.
  3. result를 출력한다.

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

public class _2644_촌수계산 {
    static LinkedList<Integer>[] relatives;
    static boolean visited[];
    static int result = -1;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        relatives = new LinkedList[n+1];
        visited = new boolean[n + 1];
        for (int i = 1; i <= n; i++) {
            relatives[i] = new LinkedList<>();
        }

        StringTokenizer st = new StringTokenizer(br.readLine());
        int targetA = Integer.parseInt(st.nextToken());
        int targetB = Integer.parseInt(st.nextToken());

        int m = Integer.parseInt(br.readLine());
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int parent = Integer.parseInt(st.nextToken());
            int child = Integer.parseInt(st.nextToken());
            relatives[parent].add(child);
            relatives[child].add(parent);
        }
        visited[targetA] = true;
        dfs(targetA, targetB, 0);
        System.out.println(result);
    }

    public static void dfs(int nowNode, int finish, int cnt) {
        // 목적지 도달
        if (nowNode == finish) {
            result = cnt;
            return;
        }
        for (int nextNode : relatives[nowNode]) {
            if (!visited[nextNode]) {
                visited[nextNode] = true;
                dfs(nextNode, finish, cnt+1);
                visited[nextNode] = false;
            }
        }
    }
}