13023번 : ABCED [Java]

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

13023번: ABCDE

 

해결 방안

DFS로 푼다. 문제에서 말하는 친구관계란 결국 깊이를 말한다. 깊이를 확인하며 친구관계가 존재함을 확인하면 1을 출력하고 종료한다.

 

전체 코드

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

public class Main {
	static int N, M;
	static ArrayList<Integer>[] list;
	static boolean[] visited;
	static boolean flag;
	static int ans = 0;

	public static void main(String[] args) throws IOException {
		BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(input.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		list = new ArrayList[N];
		for (int i = 0; i < N; i++)
			list[i] = new ArrayList<Integer>();

		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(input.readLine(), " ");
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			list[a].add(b);
			list[b].add(a);
		}

		visited = new boolean[N];
		for (int i = 0; i < N; i++) {
			dfs(i, 1);
		}

		System.out.println("0");
	}

	public static void dfs(int idx, int depth) {
		if (depth == 5) {
			System.out.println("1");
			System.exit(0);
		}

		visited[idx] = true;
		for (int i = 0; i < list[idx].size(); i++) {
			int temp = list[idx].get(i);
			if (!visited[temp]) {
				dfs(temp, depth + 1);
			}
		}
		visited[idx] = false;
	}
}