백준 13023번(ABCDE)[JAVA]

풀이

A - B, B - C, C - D, D - E 관계를 가진 A,B,C,D,E가 존재하는지 알아본다는 것은, DFS에서 A로 시작하여 DFS(B) 호출할 수 있고, B에서 DFS(C), C에서 DFS(D), D에서 DFS(E)를 호출할 수 있는 그래프이다. 즉 DFS(A)부터 탐색의 깊이가 5가 되면 이 조건을 만족할 수 있다. 탐색의 깊이가 5가 되는지 확인하는 방법은 DFS함수의 인자로 depth를 넣고 시작을 1로하여, 재귀 호출을 할 때마다 그 값을 1씩 증가시키고, 이 값이 5가 되면 flag변수 true로 바꿔주면서 문제의 관계가 존재한다는 것을 나타내면 된다.

소스 코드

import java.util.*;
import java.io.*;

public class abcde {
	static boolean[] visited;
	static ArrayList<Integer>[] arr;
	static boolean flag = false;
	
	public static void main(String[] args) throws Exception {
		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());
		
		arr = new ArrayList[n];
		visited = new boolean[n];
		
		for (int i = 0; i < n; i++) {
			arr[i] = new ArrayList<Integer>();
		}
		
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			arr[a].add(b);
			arr[b].add(a);
		}
		
		for (int i = 0; i < n; i++) {
			dfs(i, 1);
			if (flag) {
				break;
			}
		}
		
		if (flag) {
			System.out.println(1);
		}
		else {
			System.out.println(0);
		}
	}
	
	static void dfs(int v, int depth) {
		if (visited[v])
			return;
		
		if (depth == 5) {
			flag = true;
			return;
		}
		
		visited[v] = true;
		for (int i : arr[v]) {
			if (!visited[i]) {
				dfs(i, depth+1);
			}
		}
		visited[v] = false;
	}
}

태클 감사합니다.
조언 환영입니다.