문제

BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다.

오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다.

A는 B와 친구다.
B는 C와 친구다.
C는 D와 친구다.
D는 E와 친구다.

위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 사람의 수 N (5 ≤ N ≤ 2000)과 친구 관계의 수 M (1 ≤ M ≤ 2000)이 주어진다.

둘째 줄부터 M개의 줄에는 정수 a와 b가 주어지며, a와 b가 친구라는 뜻이다. (0 ≤ a, b ≤ N-1, a ≠ b) 같은 친구 관계가 두 번 이상 주어지는 경우는 없다.

출력

문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다.

풀이

결국 문제의 핵심은 Depth 5 이상인 노드를 찾는 것이다.

이것을 위해 입력값에서 Node Class를 정의하고 BackTracking을 사용하여 깊이 5 이상을 탐색하며, 가지치기를 수행하였다. (여기서 Node를 입력받을 시, 양방향으로 관계를 이어주어야 한다.)

이 과정에서 초기 입력 시 한번도 언급되지 않는 Node가 Null로 선언되는 자잘한 이슈가 있었다.

다음부터는 입력값 시 명시적으로 노드를 초기화해주어야 할 것 같다.

자세한 내용은 코드를 참조할 것

코드

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

public class Main {
    static int N, M;
    static boolean[] check;
    static int checkCnt;
    static Node[] nodeArr;
    static boolean isRemain = false;
    public static void main(String[] args) {
        input();
        //logging();
        for(int i = 0; i < N; i++) {
            check = new boolean[N]; //초기화
            backTracking(i); //logic
            if (isRemain) {
                System.out.println(1);
                return;
            }
        }
        System.out.println(0);

    }

    static void backTracking(int idx) {
        check[idx] = true;
        if (isRemain || checkLength()) { //기저조건
            isRemain = true;
            return;
        }

        for(int i = 0; i < nodeArr[idx].friends.size(); i++) {
            int next = nodeArr[idx].friends.get(i);
            if(check[next]) continue;
            backTracking(next);
            check[next] = false; //다시 false 처리
        }
    }

    static boolean checkLength() {
        int cnt = 0;
        for(boolean now : check) {
            if (now) cnt++;
            if (cnt >= 5) return true;
        }
        return false;
    }

    static void logging() {
        for(int i = 0; i < nodeArr.length; i++) {
            try{
                System.out.println(i + " : " + Arrays.toString(nodeArr[i].friends.toArray()));
            } catch (NullPointerException e) {
                System.out.println("NULL");
            }
        }
    }
    static void input() {
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            check = new boolean[N];
            nodeArr = new Node[N];
            for (int i = 0; i < N; i++) { // 모든 노드를 초기화하는 과정 추가 (99%에서 NullException 발생)
                nodeArr[i] = new Node(i);
            }

            for(int i = 0; i < M; i++) {
                st = new StringTokenizer(br.readLine());
                int num = Integer.parseInt(st.nextToken());
                int friend = Integer.parseInt(st.nextToken());
                //내 쪽 추가
                if(nodeArr[num] == null) nodeArr[num] = new Node(num, friend);
                else nodeArr[num].friends.add(friend);

                //친구 쪽 추가
                if(nodeArr[friend] == null) nodeArr[friend] = new Node(friend, num);
                else nodeArr[friend].friends.add(num);
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

}

class Node {
    int num;
    List<Integer> friends = new ArrayList<>();

    public Node (int num) { this.num = num;}
    public Node (int num, int friend) {
        this.num = num;
        friends.add(friend);
    }
}