[백준 13023번] ABCDE - java

문제 설명

1. 사람 수 N, 관계 수 M 이 주어진다.

2. 그 다음부터 M 개로 관계들이 주어진다.

3. A - B - C - D - E 이렇게 친구인지 여부를 구하면 된다.

풀이 과정

1. DFS + 백트래킹

2. 각 친구 상태를 가지는 ArrayList 를 배열로 가지면 된다.

3. 현 사람을 기준으로 모든 관계 ArrayList 를 찾고 주르륵 찾으면 된다.

4. 그리고 이전에 확인한 사람인지 체크 여부를 확인해서 백트래킹 해주면 된다.

5. 이게 잘 동작하는 이유는 어차피 이전으로 돌아가지 않으니 depth 가 차면 알아서 ABCDE 열차가 완성되기 때문이다.

코드

/******************************************************************************

 Online Java Compiler.
 Code, Compile, Run and Debug java program online.
 Write your code in this editor and press "Run" button to execute it.

 *******************************************************************************/
import java.util.*;

public class Main
{
    private static ArrayList<Integer>[] relationList;
    private static boolean check[];
    private static int ans = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int M = sc.nextInt();

        // 최초 초기화 - relationList는 모든 인원들에 대해 이 사람의 친구를 저장한다.
        relationList = new ArrayList[N];
        check = new boolean[N];
        for(int i=0; i<N; i++) relationList[i] = new ArrayList<>();

        for(int i=0; i<M; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();

            relationList[a].add(b); // 각 사람들의 친구 관계를 저장
            relationList[b].add(a);
        }

        // 모든 사람들에 대해서 A-B-C-D-E 관계가 있는지를 체크한다.
        for(int i=0; i<N; i++) {
            DFS(0, i);
        }

        System.out.println(ans);
    }

    private static void DFS(int depth, int now) {
        if (depth == 4) { // 4명까지 친구로 확인되면 정답
            ans = 1;
            return;
        }

        if (ans == 1) return;

        // 백트레킹 지금 나의 탐색 여부 확인
        check[now] = true;
        ArrayList<Integer> friendList = relationList[now]; // 내 친구들 확인

        // 그래서 그 친구들 모두에 대해 확인하면 된다.
        for(int i=0; i<friendList.size(); i++) {
            int friend = friendList.get(i);

            if (!check[friend]) {
                DFS(depth+1, friend); // 이게 되는 이유는 한번 이 사람에 대해 체크하게 되면 그 다음 친구에 대해 확인할 때 일자로 유지가 가능하다.
            }
        }

        check[now] = false;
    }
}