[백준] 13023번 : ABCDE - JAVA [자바]

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

---

dfs 알고리즘 문제이다.

N 개의 노드와 M 개의 간선이 주어졌을 때, 문제의 A, B, C, D, E 조건을 만족하는 그래프가 있는지 탐색하는 것이다.

여기서 중요한 것이 모든 노드를 들리는 간선이 있는 것이 아니고 문제의 조건을 만족하는 그래프를 탐색하는 것이기 때문에 깊이는 5 까지 탐색한다.

각 노드의 간선들을 저장한다. 예를 들어 0 7 일 경우 0 번째 인덱스에 7을 add 해준다.

그 다음 모든 노드들을 돌면서 dfs 알고리즘을 실행한다.

public static void dfs(int start, int depth) {
	// 문제의 조건에 맞는 A, B, C, D, E가 존재
    if (depth == 5) {
    	answer = 1;
    	return;
	}
    visited[start] = true;
    for (int to : edgeList[start]) {
    	if (!visited[to]) {
        	dfs(to, depth + 1);
		}
	}
    visited[start] = false;
}

우선 종료 조건을 문제의 조건에 맞는 A, B, C, D, E가 존재 하는 그래프를 찾았을 때
즉, 어떠한 노드에 갈 수 있는 간선을 선택해서 다른 노드를 선택하는 것을 반복하며 그래프를 만들 때 깊이가 5 인 그래프를 만들면 종료한다.

1. 처음 시작할때 노드를 탐색한다. visited[start] = true

2. 이 노드에서 갈 수 있는 노드를 탐색한다. for (int to : edgeList[start])

3. 그 중 아직 가지 않은 노드를 선택한다. if (!visited[to])

4. 깊이를 1 늘리고 그 노드로 넘어간다. dfs(to, depth + 1)
   4.1 또 그 노드에서 1번부터 반복한다.

5. 갈 수 있는 모든 노드를 들리고 나서는 출발할 노드를 방문 초기화 해준다. visited[start] = false

6. 문제의 조건에 맞는 그래프를 찾았으면 answer = 1 을 대입한다.

---

public class bj13023 {

    public static int answer = 0;
    public static int N;
    public static int M;
    public static ArrayList<Integer>[] edgeList;
    public static boolean[] visited;

    public static void main(String[] args) throws Exception {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String line = br.readLine();
        String[] split = line.split(" ");

        N = Integer.parseInt(split[0]);
        M = Integer.parseInt(split[1]);
        visited = new boolean[N];
        edgeList = new ArrayList[N];

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

        for (int i = 0; i < M; i++) {
            String line1 = br.readLine();
            String[] split1 = line1.split(" ");
            int from = Integer.parseInt(split1[0]);
            int to = Integer.parseInt(split1[1]);
            edgeList[from].add(to);
            edgeList[to].add(from);
        }

        for (int i = 0; i < N; i++) {
            if (answer != 1) dfs(i, 1);
        }

        bw.write(answer + "\n");

        bw.flush();
        bw.close();
        br.close();
    }

    public static void dfs(int start, int depth) {
        // 문제의 조건에 맞는 A, B, C, D, E가 존재
        if (depth == 5) {
            answer = 1;
            return;
        }
        visited[start] = true;
        for (int to : edgeList[start]) {
            if (!visited[to]) {
                dfs(to, depth + 1);
            }
        }
        visited[start] = false;
    }
}

이 문제에서 어려웠던 점은 문제의 조건 A,B,C,D,E를 이해하는 것이다.