[백준] 13023번 ABCDE - 자바

13023번: ABCDE

 

문제

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

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

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

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

 

입력

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

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

 

출력

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

 

예제 입출력

문제풀이

dfs로 그래프를 탐색해서 깊이가 5가 되면 문제의 조건에 맞는 A, B, C, D, E가 존재한다고 판단하고 1을 출력하도록 했다. 이 때, 어떤 노드를 루트노드로 지정하는지에 따라 깊이가 다르므로 모든 노드에 대해 반복문을 돌면서 루트노드를 바꿔주었다.

 

이슈1. 그래프를 어떤 방식으로 저장하느냐에 따라 실행시간이 달라진다.

1) 그래프를 인접 행렬로 저장

인접 행렬은 노드 개수 N에 대하여 NxN 배열에 모든 노드 간 연결관계를 저장하는 것이다. 이 경우, 시간초과가 났다. 노드끼리 연결됐는지 확인할 때는 빠르지만, 어떤 노드에 연결된 노드를 탐색하기 위해서는 모든 노드를 다 탐색해야 하기 때문이다.

 

2) 그래프를 인접 리스트로 저장

인접 리스트로 저장할 때는 모든 노드가 아니라 연결된 노드만 저장하기 때문에 연결된 노드를 탐색할 때, 모든 노드를 탐색할 필요가 없다.

 

이슈2. depth(그래프의 깊이)가 5인지 확인하는 코드의 위치

1) dfs 함수의 맨 처음

2) dfs 함수에서 재귀호출하기 직전

3) dfs 함수의 맨 마지막: 불필요한 dfs 호출을 다 하고 나서 depth를 확인하므로 이 경우, 시간초과

public static void dfs(int v, int depth) {
        /** 1번 위치 **/
        if (depth == 5) {
            answer = 1;
            return;
        }
        /************/

        visited[v] = true;

        for (int node : rel[v]) {
            /** 2번 위치 **/
            if (depth == 4) {
                answer = 1;
                return;
            }
            /************/
            
            if (!visited[node]) {
                dfs(node, depth + 1);
            }
        }

        // 방문했던 노드 삭제
        visited[v] = false;

        /** 3번 위치 **/
        if (depth == 5) {
            answer = 1;
            return;
        }
        /************/

    }

 

정답 코드

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

public class Main {
    static int N;
    static ArrayList<Integer>[] rel;
    static boolean[] visited;
    static int answer = 0;

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

        N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        rel = new ArrayList[N];
        visited = new boolean[N];

        for (int i = 0; i < N; i++) {
            rel[i] = new ArrayList<>();
        }

        // 인접리스트 만들기
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(reader.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            rel[a].add(b);
            rel[b].add(a);
        }

        // 모든 노드를 탐색하면서 루트 노드 변경해보기
        for (int i = 0; i < N; i++) {
            visited = new boolean[N];
            dfs(i, 1);
            if (answer == 1) break;
        }

        System.out.println(answer);
    }

    public static void dfs(int v, int depth) {
        visited[v] = true;

        for (int node : rel[v]) {
            if (depth == 4) {
                answer = 1;
                return;
            }
            if (!visited[node]) {
                dfs(node, depth + 1);
            }
        }

        // 방문했던 노드 삭제
        visited[v] = false;

    }
}