[자바] 백준 13023 : ABCDE / 그래프, DFS 풀이

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

13023번: ABCDE

골드5 난이도의 정답률 약 29% 난이도의 문제입니다.

그래프를 구현한 후 dfs로 탐색하는 결합 유형입니다.

---

문제 분석

친구 관계를 구하는 문제입니다.

문제에서 주어진 예시를 통해 문제를 간단하게 풀이하자면 다음과 같습니다.

​

문제 예시는 A-B-C-D-E 관계를 찾으라는 말은

0 ~ N-1개의 주어진 것에서 노드가 쭉 연결되었는지를 찾는 문제입니다.

 

하지만, 위와 같은 경우 1번이 가운데에 있고 2,3,4번이 1번과 친구 관계입니다.

이 경우에 2번과 3번, 4번은 각각 남남이라고 보면 됩니다.

즉 친구의 친구는 친구로 간주하지 않습니다.

​

이런 경우가 아닌 '일직선'인 관계를 찾는 것이 문제의 핵심입니다.

쉽게 말하면 한붓그리기 같은 느낌이라고 생각하시면 됩니다.

 

​

문제 풀이

문제를 이해 했으니, 문제를 풀이해야합니다.

먼저 문제를 어떻게 풀이할지 간단하게 계획을 세워보겠습니다.

​

먼저 주어지는 입력인 친구 관계를 그래프로 표현해줘야합니다.

그리고 그래프로 표현된 친구 관계에서 DFS를 통해서 한붓그리기처럼 연결되어있나 확인하면 됩니다.

​

문제를 풀다가 알았는데, 0~n-1까지 DFS를 돌릴 때 주의할 점이 딱 한 가지가 있습니다.

0~n-1번까지 순서대로 한붓그리기가 되면 좋겠지만, 그러지 않을 수가 있습니다.

for문을 돌릴 때 0~n-1까지 탐색을 할텐데, 이 경우에 노드를 순번대로 한붓으로 그리는 경우 visited 처리가 된 노드를 갈 수 있습니다. (예제 2번 같은 경우)

​

따라서 백트래킹처럼 dfs를 돌리고 나서 방문했던 노드 기준으로 !visited 처리를 해주셔야합니다.

​

따라서 문제는 다음과 같은 순서로 푸시면 됩니다.

1. 기초 데이터 셋업
2. 그래프 구현
3. dfs를 통한 탐색

​

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

public class Main {
    private static final Scanner sc = new Scanner(System.in);
    private static int n, m;
    private static int answer = 0;
    private static ArrayList<Integer>[] list;
    private static boolean[] visited;

    public static void main(String[] args) {
        initData();
        setupGraph();
        findAnswer();
    }

    private static void initData() {
        n = sc.nextInt();
        m = sc.nextInt();

        list = new ArrayList[n];
        visited = new boolean[n];

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

    private static void setupGraph() {
        for (int i = 0; i < m; i++) {
            int vertex1 = sc.nextInt();
            int vertex2 = sc.nextInt();
            list[vertex1].add(vertex2);
            list[vertex2].add(vertex1);
        }
    }

    private static void findAnswer() {
        for (int i = 0; i < n; i++) {
            if (answer == 0) {
                dfs(i, 1);
            }
        }
        System.out.println(answer);
    }

    private static void dfs(int start, int depth) {
        if (depth == 5) {
            answer = 1;
            return;
        }

        visited[start] = true;
        for (int i = 0; i < list[start].size(); i++) {
            int next = list[start].get(i);
            if (!visited[next]) {
                dfs(next, depth + 1);
            }
        }
        visited[start] = false;
    }
}