[BOJ] 13023. ABCDE - Graph

[BOJ] 13023. ABCDE - Graph

Problem

제출일 : 2020-02-03

문제 풀이 시간 : 1H

난이도 : ★★☆

---

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

BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다.

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

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

위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오.

Constraints

학생의 수는 1000명이며, 각 학생의 점수는 0점 이상 100점 이하의 값이다.

input

첫째 줄에 사람의 수 N (5 ≤ N ≤ 2000)과 친구 관계의 수 M (1 ≤ M ≤ 2000)이 주어진다.

둘째 줄부터 M개의 줄에는 정수 a와 b가 주어지며, a와 b가 친구라는 뜻이다. (0 ≤ a, b ≤ N-1, a ≠ b) 같은 친구 관계가 두 번 이상 주어지는 경우는 없다.

Output

문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다.

Example

input

5 4
0 1
1 2
2 3
3 4

output

1

Solution & Inpression

문제는 일반적인 그래프 탐색문제로 테스트케이스를 맞추는것은 쉽게 풀수 있다. N의 수가 최대 2000으로 문제를 해결할때 완전탐색을 하다 중간에 답을 찾게되면 더 이상 탐색을 하지 않고 멈춰야 한다고 생각을 했다.

하지만 첫 제출때 시간초과가 나 BFS로도 문제를 풀어보고 여러 제약조건들을 추가해 봤지만 시간 초과를 벗어나진 못했다.

관계의 수 M이 작기 때문에 희소행렬로 볼수가 있으므로 인접행렬을 이용하여 문제를 해결하는것보다 인접리스트를 이용하여 문제를 해결하는것이 더 빠른 성능을 낼 수 가 있었다.

Code

언어 : JAVA

메모리 : 22684kb

실행시간 : 436 ms

import java.util.ArrayList;
import java.util.Scanner;

class Main {
    static int N, M, ans;
    static ArrayList<Integer>[] graph;
    static boolean[] visit;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        graph = new ArrayList[N];
        for (int i = 0; i < N; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int i = 0; i < M; i++) {
            int s = sc.nextInt();
            int e = sc.nextInt();
            graph[s].add(e);
            graph[e].add(s);
        }
        ans = 0;
        visit = new boolean[N];
        for (int i = 0; i < N; i++) {
            DFS(i, 1);
            if (ans == 1)
                break;
        }
        System.out.println(ans);
    }

    private static void DFS(int i, int depth) {
        if (depth == 5 || ans == 1) {
            ans = 1;
            return;
        }
        visit[i] = true;
        for (int j = 0; j < graph[i].size(); j++) {
            if (!visit[graph[i].get(j)]) {
                visit[graph[i].get(j)] = true;
                DFS(graph[i].get(j), depth + 1);
                visit[graph[i].get(j)] = false;
            }
        }
        visit[i] = false;
    }
}