[BOJ] 13023번 - ABCDE (Java)

🛠️ 문제 🛠️

---

🗒️ 설명 🗒️

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

우선 여기서 알 수 있는 것은 N명 중 5명이 이와 같은 관계를 가지고 있으면 된다.

이러한 친구 관계를 구하기 위해서는 깊이 우선 탐색을 하여 구할 수 있다.

그래프의 깊이가 5이상일 경우 위와 같은 관계가 존재한다는 것을 알 수 있다.

 

단, 이는 판별만 하면 되기 때문에 관계를 발견하면 모든 탐색을 멈출 수 있도록 했다.

---

🍀 풀이 🍀

package Baekjoon;

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

public class DFS13023 {

    static ArrayList<Integer>[] friendship;
    static boolean[] visited;
    static boolean flag; //결과 판별 변수

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        visited = new boolean[n];
        friendship = new ArrayList[n];
        for(int i = 0; i < n; i++) {
            friendship[i] = new ArrayList<>();
        }
        flag = false;

        for(int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            friendship[x].add(y);
            friendship[y].add(x);
        }

        for(int i = 0; i < n; i++) {
            visited[i] = true;
            dfs(i, 1);
            visited[i] = false;
            if(flag) { //이미 관계가 존재할 경우
                break;
            }
        }

        if(flag) {
            bw.write("1");
        }
        else {
            bw.write("0");
        }
        bw.flush();
        bw.close();
    }

    static void dfs(int c, int count) {
        if(count == 5) { //depth가 5인 경우
            flag = true;
            return;
        }
        if(flag) { //이미 관계가 존재할 경우
            return;
        }
        for(int i : friendship[c]) {
            if(!visited[i]) {
                visited[i] = true;
                dfs(i, count + 1);
                visited[i] = false;
            }
        }
    }
}