[Java] 백준_ABCDE_13023

문제

분석

DFS 문제. 친구 A,B,C.. 를 정점으로 보고, 'A는 B와 친구다'라는 것 간선으로 이해할 수 있다.

결국  양방향 그래프로 표현할 수 있다. 

 

처음에 문제 주어지는 '이와 같은 관계'가 정확히 어떤 관계인지 몰라서 이해하기가 힘들었다. 결론적으로 각 노드(친구)를 1번만 지나쳐서 5개의 노드가 연결될 수 있느냐라는 관계(DFS방식)으로 해석할 수 있다. 테스트케이스에 대입해서 이해하면 쉽다.

 

정점이 많은 경우 시간복잡도를 생각해서 인접행렬보다는 인접리스트로 그래프를 표현하는 것이 좋다. 결국 위의 관계만 찾으면 되므로 깊이가 4가 되면 dfs를 멈추고 1을 출력하면 된다. 

 

이 문제는 모든 관계 중 하나의 관계만 깊이가 4(5명이 나란히 연결)가 되는 것을 찾으면 된다. 그렇기 때문에 중간에 그러한 관계를 찾은 다음에 이후에는 탐색을 할 필요가 없다. 

소스코드

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

public class ABCDE_025 {
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    static boolean[] checked;
    static int answer;

    public static void dfs(int node, int depth) {
        if (depth == 4 || answer == 1) {
            answer = 1;
            return;
        }
        else {
            for (Integer v : graph.get(node)) {
                if (!checked[v]) {
                    checked[v] = true;
                    dfs(v, depth+1);
                    checked[v] = false;
                }
            }
        }
    }
    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());
        for (int i=0; i<N; i++) {
            graph.add(new ArrayList<>());
        }
        checked = new boolean[N];
        for (int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            int S = Integer.parseInt(st.nextToken());
            int E = Integer.parseInt(st.nextToken());
            graph.get(S).add(E);
            graph.get(E).add(S);
        }
        for (int i=0; i<N; i++) {
            checked[i] = true;
            dfs(i,0);
            checked[i] = false;
        }

        System.out.println(answer);
    }
}

결과

새로 배운 점

• 하나의 관계를 찾고 난 후에 무의미한 탐색을 멈추는 방법에는 여러가지가 있었다. 정답으로 가는 길이 1개라는 생각을 접어두자
  • 하나의 관계를 찾고난 후 1을 출력한 후  System.exit(0)으로 프로그램을 종료하는 코드도 있었다. 뭔가 강제 종료하는 느낌이 들지만 내부적으로 안전하게 정리한 후 종료하는 정상적인 방법이다. main()도 내부적으로 exit(0)을 사용한다.