백준 13023 : ABCDE [JAVA]

[문제 링크]

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

[난이도]

- Gold 5

 

[알고리즘]

- 백트래킹

 

[코드]

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

public class Main {
    static int N, M;
    static ArrayList<ArrayList<Integer>> adj;
    static boolean[] visited;
    static boolean found = false;

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        adj = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            adj.add(new ArrayList<>()); // 정점의 수만큼 생성
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            adj.get(a).add(b); // 양방향 간선
            adj.get(b).add(a); // 양방향 간선
        }

        visited = new boolean[N];

        for (int i = 0; i < N; i++) {
            if (!found) { // ABCDE가 존재하면 true 발견하지 못했다면 false
                dfs(i, 0);
            }
        }

        System.out.println(found ? 1 : 0);
    }

    static void dfs(int node, int depth) {
        if (depth == 4) { // depth가 4면 ABCDE가 서로 연결되어있다는 뜻
            found = true;
            return;
        }

        visited[node] = true;

        for (int next : adj.get(node)) {
            if (!visited[next]) { // 중복방문을 방지
                dfs(next, depth + 1);
                if (found) return;
            }
        }

        visited[node] = false; // 완전탐색을위해 다시 false로 변경
    }
}

[풀이]

이중 ArrayList로 인정리스트인 Adjacency list를 선언해준후.

각 정점을 기준으로 dfs를 반복해 depth가 4인경우를 찾아준다.

depth가 4일경우 ABCDE가 친구인 경우이다.

찾았다면 1을 못찾았다면 0을 출력한다.