[백준] ABCDE(13023)

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

DFS 탐색을 통해 해결하는 문제이다. 주어진 ABCDE의 관계를 만족하려면 재귀함수 호출의 깊이가 5 이상인 관계가 최소한 한개라도 존재하면 되는 것이다.

그림 1, 2번은 깊이가 5이므로 당연히 만족하고 3번 또한 0 - 4 - 3 - 7 - 1와 같이 깊이가 5인 관계가 존재하므로 문제 조건을 만족하여 1을 출력한다.

하지만 그림 4번의 경우 어떤 노드에서도 깊이가 5인 관계가 존재하지 않아 문제 조건을 만족하지 못하고 0을 출력하게 된다.

또한 N과 M의 최댓값이 2000이므로 한 노드에 대한 시간복잡도는 $O(2000 + 2000 = 4000)$이 된다.

최대 노드의 개수가 2000개 이므로 $2000 × O(4000) = 8,000,000$의 연산량이 필요한데, 파이썬은 못해도 1초에 10,000,000을 계산할 수 있으므로 충분하다.

따라서 문제풀이 방법은 다음과 같다.

1. arrive 불린을 따로 선언하여 재귀함수 호출의 깊이가 5에 도달하는 경우 함수를 종료한 후 1 출력

2. 모든 노드에 대해 탐색하였으나 재귀함후 호출의 깊 이가 5에 도달하지 못한 경우 0 출력

Python

import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

N, M = map(int, input().split())
A = [[] for _ in range(N)] # 인접리스트
visited = [False] * N # 방문리스트

# depth가 5에 도달했는지 체크하는 불린
arrive = False

def DFS(v, depth):
    global arrive

    # 만약 depth가 5에 도달했다면
    # 문제에서 요구하는 ABCDE 관계를 발견했다면
    if depth == 5:
        arrive = True
        return # 함수 종료
    
    visited[v] = True
    for i in A[v]:
        # 방문하지 않은 노드에 대해 depth를 1씩 증가시키며 탐색
        if not visited[i]:
            DFS(i, depth + 1)

    # 탐색이 끝난 후에는 다시 False로 초기화
    visited[v] = False

for _ in range(M):
    a, b = map(int, input().split())

    A[a].append(b)
    A[b].append(a)

for i in range(N):
    if not visited[i]:
        DFS(i, 1)
    
    # depth가 5인 관계(ABCDE 관계)를 찾은 경우라면 반복문 탈출 
    if arrive:
        break

if arrive:
    print(1)
else:
    print(0)

Java

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

public class P_13023 {

    static ArrayList<Integer>[] A;
    static boolean[] visited;
    static boolean result;

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

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

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

        for (int i = 0; i < N; i++) {
            A[i] = 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());

            A[a].add(b);
            A[b].add(a);
        }

        result = false;
        for (int i = 0; i < N; i++) {
            if (result)
                break;

            DFS(i, 1);
        }

        if (result) System.out.println(1);
        else System.out.println(0);
    }

    static void DFS(int v, int depth) {
        if (depth == 5 || result) {
            result = true;
            return;
        }

        visited[v] = true;
        for (int i : A[v]) {
            if (!visited[i]) {
                DFS(i, depth + 1);
            }
        }
        visited[v] = false;
    }
}

한 가지 주의해야 할 점은 DFS 탐색이 끝난 후 모든 노드에 대해 방문 리스트를 다시 False로 초기화해주어야 한다는 점이다.

만약 초기화를 안해주게 되면 발생할 수 있는 문제점은 다음과 같다.

첫 노드에서 깊이가 5인 관계를 찾지 못하고 DFS 탐색이 종료된 경우, 다음 노드에서 사용해야할 방문리스트가 이전에 첫 노드에서 사용한 방문리스트를 그대로 들고 사용하기 때문에 알고리즘에 문제가 생긴다.

그리고 depth가 5인(ABCDE 관계)를 찾은 경우라면 반복문을 탈출한 다음 프로그램을 바로 종료하도록 하여 비효율적인 연산을 줄일 수 있다.