백준 13023 - ABCDE

문제 파악

DFS의 깊이가 4인 친구 관계 체인이 존재하는지 확인하는 문제
-> 깊이가 4 : 5명의 친구가 주루룩 이어지는지를 확인
-> 중복 없이 5개의 노드가 주루룩 연결되어야 함 (1번에서 시작해서 4번 연결하면 5명이 연결됨)

DFS로 풀어야 함!
친구 관계가 0 - 1 - 2 - 3 - 4일 때,
0번과 1번은 친구 (연결)
1번과 2번은 친구 (연결)
2번과 3번은 친구 (연결)
3번과 4번은 친구 (연결)
이므로 재귀함수로 반복해서 깊이 들어갈 수 있다.

풀이

1. 버퍼리더와 스트링 토크나이저를 사용해 친구 수 N과 친구 관계의 수 M을 입력받는다.

2. 그래프를 저장할 인접 리스트에 입력 값을 넣는다.
   a. 인접 리스트를 생성한다.
   b. 인접 리스트의 각 ArrayList를 초기화 한다.
   c. 입력 받은 값을 리스트에 넣어주기

   여기서 궁금했던 점 1 : 왜 인접 리스트를 생성하고 for문을 통해 ArrayList를 초기화 하는지 ?
   -> 인접 리스트를 생성하는 것은 '칸'을 만들어 놓은 것
   초기화를 통해 각 칸에 실제로 ArrayList를 만들어 넣어주는 의미어주는 의미
   2 : ArrayList를 사용하는 이유는 이 문제에서 중간에 삽입 / 삭제를 하지 않고 쭉 읽기만 하면 되기 때문에 이게 더 빠름!!

3. 각 노드마다 DFS 실행
   a. 만약 찾으면 종료한다.

4. 찾으면 1 출력, 아니면 0 출력

5. DFS 함수
   a. 노드와 깊이를 인자로 받는다.
   b. 만약 깊이가 4면 찾음!
   c. 아니라면 현재 노드를 방문 처리 해주고
   d. 다음 노드를 찾고 재귀를 호출한다.
   e. 재귀를 돌았는데 못찾으면 백트래킹(현재 노드 방문 x) 해주어 다시 다음 노드를 찾게 만들어줌

코드

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

public class ABCDE {
    static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    static ArrayList<Integer>[] graph;
    static boolean[] visited;
    static boolean found;

    public static void main(String[] args) throws IOException{
        StringTokenizer st = new StringTokenizer(bf.readLine());

        //친구 수(노드 수)
        int N = Integer.parseInt(st.nextToken());
        //친구 관계의 수(간선 수)
        int M = Integer.parseInt(st.nextToken());

        //객체 배열 초기화
        graph = new ArrayList[N];

        //ArrayList 초기화
        for (int i=0; i<N; i++) {
            graph[i] = new ArrayList<>();
        }

        //입력 값 리스트에 넣어주기
        for (int i=0; i<M; i++) {
            st = new StringTokenizer(bf.readLine());
            //왼쪽 노드(시작 노드)
            int a = Integer.parseInt(st.nextToken());
            //오른쪽 노드
            int b = Integer.parseInt(st.nextToken());

            //노드 연결
            graph[a].add(b);
            graph[b].add(a);
        }

        //방문 배열 초기화
        visited = new boolean[N];

        //dfs 수행
        for (int i=0; i<N; i++) {
            dfs(i, 0);
            if (found) {
                break;
            }
        }

        //found가 true면 1, 아니면 0 출력
        if (found) {
            System.out.println(1);
        } else {
            System.out.println(0);
        }
    }

    public static void dfs(int current, int depth) {
        //깊이가 4이면 찾았다!
        if (depth == 4) {
            found = true;
            return;
        }

        //현재 노드 방문 처리
        visited[current] = true;

        //다음 노드 찾기
        for (int next : graph[current]) {
            if (!visited[next]) {
                dfs(next, depth+1);
                if (found) {
                    return;
                }
            }
        }

        //백트래킹
        visited[current] = false;
    }
}