[백준] 13023번 - ABCDE (Java)(△)

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

13023번: ABCDE

 

<문제 풀이>

1. 인접리스트 방식으로 입력값을 저장한다.

2. 중복값을 값을 허용하지 않기 때문에 방문배열을 사용한다.

3. 친구관계는 A-B, B-C, C-D, D-E로 4개로 고정이 되어 있다. 따라서 호출 level이 5가 되면 친구관계를 다 찾은 것이다.

5. level == 5이면 더 이상 다른 친구관계를 찾을 필요없이(가지치기) 1을 출력하고 종료하면 된다.

6. 그래프의 시간복잡도 O(V + E)이므로 2,000 + 2,000 = 4,000, 모든 노드에 대한 탐색은 4,000 * 2,000 = 8,000,000이다. 

 

<구현>

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

public class Main {
    static int N, M;
    static ArrayList<Integer> A[];
    static boolean visited[];
    static boolean arrived;

    void DFS(int now, int level) {
        // 종료조건
        if (level == 5) {
            arrived = true;
            return;
        }

        // 재귀호출
        visited[now] = true;
        for (int i : A[now]) {
            if (visited[i]) continue;
            DFS(i, level+1);
        }
        // 재귀호출에서 돌아오면 새로운 탐색을 위해 방문배열을 원복한다.
        visited[now] = false;
    }

	void Solve() {
        for (int i=0; i<N; i++) {
            DFS(i, 1);
            if (arrived) break;
        }

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

    void inputData() throws Exception {
        InputStreamReader reader = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(reader);
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        A = new ArrayList[N];
        visited = new boolean[N];
        for (int i=0; i<N; i++) {
            A[i] = new ArrayList<Integer>();
        }
        for (int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            A[s].add(e);
            A[e].add(s);
            
        }
    }

    public static void main(String[] args) throws Exception {
        Main m = new Main();
        m.inputData(); // 입력 받는 부분
        m.Solve();// 여기서부터 작성
    }
}