[백준 2644번] 촌수 계산 (Java 풀이)

백준알고리즘 2644번 : 촌수 계산 (Solved.ac 난이도 Gold5)

 

 

https://www.acmicpc.net/problem/2644

2644번: 촌수계산

 

 

촌수를 이동함에 따라 count를 해주어야하는 부분에서 약간 헤멨다.

특이사항이 있다면, 일반적인 dfs와는 달리 한번 check한 LinkedList에 대해서는 다시 확인을 할 필요가 없다는 점이다.

그렇게 해도 되는 이유는 문제에서 '각 사람의 부모는 최대 한 명만 주어진다.'라고 명시되어 있기 때문이다.

이로 인해 tree 구조가 성립되어, 구하고자하는 node기준으로 윗방향이든, 아랫방향이든 한번씩만 탐색하면 된다.

따라서 기존 node를 다시 탐색하지 않도록 flag를 바꿔주기만하고 (부모 노드와 자식 노드의 탐색을 반복하지
않게하기 위해서) 원복시키지는 않았다.

 

 

 

풀이 과정

---

1. 찾아야하는 node 번호를 static 변수(y)로 입력한다.
2. 해당 변수가 나올 때까지 대상 변수(x)를 기준으로 재귀를 이용하여 LinkedList를 탐색한다.
2-1. 해당 LinkedList에 연결된 숫자들이 위로 부모 node인지 자식 node인지는 중요하지않다.
      다만 기존 node를 다시 탐색하지 않도록 check할 수 있는 flag를 통해 한번씩 탐색하도록 한다.
3. 대상 변수 y를 발견하면 재귀를 돌리는 동안 하나씩 쌓은 instance 변수를 답으로 출력하도록 한다.
3-1. 발견하지 못하면 -1을 출력하도록 한다.

 

 

소스 ▽

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

public class Main {// [Silver2] No2644 : 촌수계산
    static ArrayList<Integer>[] arr;
    static boolean[] chk;
    static int y;
    static int ans = -1;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        arr = new ArrayList[num + 1];
        for (int i = 0; i < num + 1; i++) {
            arr[i] = new ArrayList<>();
        }
        chk = new boolean[num + 1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        int x = Integer.parseInt(st.nextToken());
        y = Integer.parseInt(st.nextToken());
        int leng = Integer.parseInt(br.readLine());
        for (int i = 0; i < leng; i++) {
            st = new StringTokenizer(br.readLine());
            int tmp1 = Integer.parseInt(st.nextToken());
            int tmp2 = Integer.parseInt(st.nextToken());
            arr[tmp1].add(tmp2);
            arr[tmp2].add(tmp1);
        }
        dfs(x, 0);
        System.out.println(ans);
    }

    public static void dfs(int x, int cnt) {

        chk[x] = true;

        for (int a : arr[x]) {
            if (a == y) {
                ans = ++cnt;
                return;
            }
            if (chk[a] == false) {
                cnt++;
                dfs(a, cnt);
                cnt--;
            }
        }

    }
}