13023 - ABCDE[G5]

문제

문제

 

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);
    }
}