[Java] 백준 13023번 - ABCDE

#13023 - ABCDE

---

 

 

난이도 : 골드 5

문제 유형 : DFS/그래프 탐색

 

https://www.acmicpc.net/problem/13023

 

 

문제 분석

---

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

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

 

A-B-C-D-E 라는 관계가 성립하는 노드,엣지를 구하는거라는 건 알겠는데 이걸 어떻게 구할지 생각이 잘 나지 않았다.

 

예제 2번을 보면

 

0 - 1 - 3

1 - 0 - 2 - 4

2 - 1 - 3

3 - 2 - 0

4 - 1
위와 같은 인접리스트가 만들어진다.

 

이 문제가 요구하는 바는 간단하게 0 - 3 - 2 - 1 - 4 와 같이 depth가 5 이상인 관계가 만들어지면 출력이 1, 만들어지지 않으면 0인 것이다.

 

노드 순서대로 계속 DFS를 진행하며 그냥 depth가 5이상인 관계가 존재하는지 여부를 파악해주면 된다.

 

한 노드에서 출발한 모든 경로를 탐색하기 위해 dfs 마지막에 노드 방문 여부를 다시 false로 설정해주었다.

 

 

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

public class Main {
    private static int n, m;
    private static ArrayList<Integer>[] matrix;
    private static boolean[] visited;
    private static boolean arrive;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] st = br.readLine().split(" ");
        n = Integer.parseInt(st[0]);
        m = Integer.parseInt(st[1]);

        matrix = new ArrayList[n];
        visited = new boolean[n];

        for (int i = 0; i < n; i++) {
            matrix[i] = new ArrayList<Integer>();
        }
        for (int i = 0; i < m; i++) {
            String[] input = br.readLine().split(" ");
            int x = Integer.parseInt(input[0]);
            int y = Integer.parseInt(input[1]);
            matrix[x].add(y);
            matrix[y].add(x);
        }
        for (int i = 0; i < n; i++) {
            dfs(i, 1);
            if (arrive) {
                break;
            }
        }
        if (arrive) {
            System.out.println(1);
        } else {
            System.out.println(0);
        }
    }
    public static void dfs(int idx, int depth) {
        if (depth >= 5) {
            arrive = true;
            return;
        }
        visited[idx] = true;

        for (int i : matrix[idx]) {
            if (!visited[i]) {
                dfs(i, depth + 1);
            }
        }
        visited[idx] = false;
    }
}