[java] 백준 13023번 문제(ABCDE)

원본 링크 : https://www.acmicpc.net/problem/13023

---

문제설명

 

 

소스코드

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

public class Boj_13023
{
    static boolean[] visited; // 방문 배열
    static ArrayList<Integer>[] adjacencyList; // 인접 리스트

    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()); // 엣지 개수

        visited = new boolean[n];
        adjacencyList = new ArrayList[n];
        for(int i = 0; i < adjacencyList.length; ++i) adjacencyList[i] = new ArrayList<>();

        for(int i = 0; i < m; ++i)
        {
            st = new StringTokenizer(br.readLine());
            int v = Integer.parseInt(st.nextToken());
            int u = Integer.parseInt(st.nextToken());
            adjacencyList[v].add(u);
            adjacencyList[u].add(v);
        }

        for(int i = 0; i < n; ++i)
        {
            if(!visited[i])
            {
                if (DFS(i, 1))
                {
                    System.out.println(1);
                    return;
                }
            }
        }
        System.out.println(0);
    }

    static boolean DFS(int num, int depth)
    {
        if(depth == 5) return true; // 깊이가 5라면 메서드 종료 및 true 리턴
        visited[num] = true; // 방문 처리
        for(int i : adjacencyList[num]) // 해당 인접 리스트 순회
        {
            if((!visited[i]) && (DFS(i, depth + 1))) return true; // 재귀의 리턴 값이 ture 라면 true 리턴
        }
        // 메서드가 종료되지 않았다면(true를 리턴받지 못했다면)
        visited[num] = false; // 방문 처리 취소(다른 경로에서 num을 방문할 수 있도록)
        return false;
    }
}

 

설명

• 주어진 모든 노드에 DFS를 수행하고 재귀의 깊이가 5이상이면 1, 아니면 0을 출력하면 된다.
• DFS의 시간 복잡도는 O(V + E)이므로 4000이고, 이를 최대 2000번 반복하니까 8,000,000번의 연산이 수행되고 자바는 대략 1초에 1억번 연산을 수행할 수 있으니 여유로운 연산량이다.

 

아래의 테스트 케이스를 예로 들면

먼저 그래프 데이터를 인접 리스트로 저장한다.

 

모든 노드에서 DFS를 수행한다. 수행할 때 재귀 호출마다 깊이를 더한다.

깊이가 5가되면 1을 출력하고 프로그램을 종료한다.

 

아래 코드는 DFS 메서드에 출력문을 더한 코드이다.

static boolean DFS(int num, int depth)
{
    System.out.print(num + "(depth " + depth +") -> ");
    if(depth == 5) return true; // 깊이가 5라면 메서드 종료 및 true 리턴
    visited[num] = true; // 방문 처리
    for(int i : adjacencyList[num]) // 해당 인접 리스트 순회
    {
        if((!visited[i]) && (DFS(i, depth + 1))) return true; // 재귀의 리턴 값이 ture 라면 true 리턴
    }
    System.out.println();
    // 메서드가 종료되지 않았다면(true를 리턴받지 못했다면)
    visited[num] = false; // 방문 처리 취소(다른 경로에서 num을 방문할 수 있도록)
    return false;
}

 

 

아래의 테스트 코드에서 출력문 결과는