[13023번] ABCDE ( dfs, dfs 빠져나오면서 방문 배열 초기화, dfs 흐름 )

---

---

✅ 방문 배열 초기화

각 노드들이 dfs를 실행하기 전에 방문 배열을 false해주는 것과
dfs가 끝난 후에 방문 배열을 false해주는 것의 차이가 뭘까.!

-> dfs가 끝난 후에 방문 배열을 false해주면 밑에서 한 칸씩 위로 올라오는 코드이고, 각 노드들이 실행 전에 방문 배열을 false 해주면 밑에서 한 칸씩 위로 올라오지 않고 그대로 dfs가 종료되므로 한 칸 씩 위로 올라와서 방문 안 한 배열을 탐색하지 않는다.

손으로 나타내보면, 이런 차이가 존재한다.

 for (int i = 0; i < node; i++) {
			visited[i] = false;
			dfs(i, 1);
			//	if (arrive) break;
		}          

private static void dfs(int node, int depth) {
		visited[node] = true;
		if (depth == 5) {
			arrive = true;
			return;
		}
		for (int i : A[node]) {
			if (!visited[i]) {
				dfs(i, depth + 1);
			}
		}
		visited[node] = false;
	}

---

✅ 코드

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

public class Main {

	static ArrayList<Integer>[] A;
	static boolean visited[];
	static boolean arrive;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		int node = Integer.parseInt(st.nextToken());
		int edge = Integer.parseInt(st.nextToken());

		A = new ArrayList[node];
		visited = new boolean[node];

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

		for (int i = 0; i < edge; i++) {
			st = new StringTokenizer(br.readLine());
			int sNode = Integer.parseInt(st.nextToken());
			int eNode = Integer.parseInt(st.nextToken());
			A[sNode].add(eNode);
			A[eNode].add(sNode);
		}

		for (int i = 0; i < node; i++) {
			//visited[i] = false;
			dfs(i, 1);
			if (arrive) break; //이거 안 해주면 0에서 탐색했을 때 depth가 5여도 1,2,3, 모두를 탐색한다.
			//노드 0 일 때 5가 아니면 1,2,3... 모두를 탐색해야 하는 것이지 depth가 5라면 탐색을 노드 0에서 끝낸다.
		}
		if (arrive) {
			System.out.println(1);
		} else {
			System.out.println(0);
		}
	}

	// 재귀
	private static void dfs(int node, int depth) { //이 코드에서 노드 0으로 시작했을 때  
		// depth=5일 때 바로 끝나지 않고 다시 거슬러 올라가면서 다 탐색해서 false 해주고 끝난다.
		visited[node] = true;
		if (depth == 5) {
			arrive = true;   v                              
			return; //for문의 dfs 코드로 가는데, 만약에 위에 for문에서  if (arrive) break; 가 없으면 안 빠져 나가고 1,![](https://velog.velcdn.com/images/super-hwang/post/495dcbc3-c7a8-42b0-b7b0-28bd47dfbc96/image.jpg)
2,3..의 for문이 계속 실행된다.
		}
		for (int i : A[node]) {
			if (!visited[i]) {
				dfs(i, depth + 1);
			}
		}
		visited[node] = false; //depth에서 하나씩 빠져나오면서 실행하는거
	}
}

---