[백준] 13023: ABCDE 문제 풀이

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

접근 방식

이번 문제는 그래프 탐색 문제로, AB, BC, CD, DE의 친구관계가 있는지 가능한 모든 경우의 수를 검사하여 확인한다.
즉 탐색 시 트리의 깊이가 4단계가 올 수 있으면 가능한 것이고, 그렇지 않다면 불가능하다.

1. 인접 리스트를 생성하여 친구 관계를 입력 받되, 친구 관계는 일방적인 관계가 아니므로 양방향 그래프로 만들어준다.

2. 어디서 출발하든 깊이가 4인 경우만 있으면 되기 때문에 0부터 N까지 반복하면서 루트 번호를 바꾸어가며 dfs탐색을 진행한다.

3. 각 노드 방문처리를 진행하면서 깊이 탐색을 들어가고, 깊이가 4가 되면 true를 리턴, 끝까지 갔는데 4가 되지 않으면 빠져나오면서 방문처리를 취소한다.

전체 코드

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

public class Main {
	static int N, M;
	static List<Integer>[] g;
	static boolean [] v;
	
	static boolean dfs(int n, int cnt) {
		if (cnt == 4) return true;
		v[n] = true;
		for (int i:g[n]) if (!v[i]&&dfs(i, cnt+1)) return true;
		v[n] = false;
		return false;
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		g = new List[N];
		for (int i = 0; i < N; i++) g[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());
			g[a].add(b); g[b].add(a);
		}
		int ans = 0;
		for (int i = 0; i < N; i++) {
			v = new boolean[N];
			if(dfs(i, 0)) ans = 1;
		}
		System.out.println(ans);
	}
}