[백준 골드 5] 13023번: ABCDE

문제

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

13023번: ABCDE

 

풀이

• N명의 사람이 0부터 N-1번까지 번호가 매겨져 있고, 이 중 일부 사람들은 친구이다.
• 이때, A와 B가 친구이고, B와 C가 친구이고,  C와 D가 친구이고,  D와 E가 친구가 되는 친구 관계 A, B, C, D, E가 존재한다면 1, 아니면 0을 출력한다.

 

문제 이해가 잘 안됐지만, A -> B -> C -> D -> E 처럼 일렬로 나열할 수 있는 그래프가 존재하는지 판별하는 것이 핵심이었다.

재귀가 몇 번 일어났는지 판별하기 위해서 depth를 사용해서 5번까지 일어난다면 1을 출력하도록 한다.visit은 재귀가 종료되면서 다음에 실행될 탐색을 위해 다시 false로 돌려놓는다.

public static void dfs(int number, int depth) {
    if (depth == 5 || flag) {
        flag = true;
        return;
    }

    visited[number] = true;

    for (int target : graph.get(number)) {
        if (!visited[target]) {
            dfs(target, depth + 1);
        }
    }

    visited[number] = false;
}

 

 

전체 코드 (Java)

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

public class Main {

	static int N, M;
	static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
	static boolean[] visited;
	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());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		visited = new boolean[N];
		for (int i = 0; i < N; i++) {
			graph.add(new ArrayList<>());
		}

		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());

			graph.get(a).add(b);
			graph.get(b).add(a);
		}

		for (int i = 0; i < N; i++) {
			dfs(i, 1);

			if (flag)
				break;
		}

		System.out.println(flag ? 1 : 0);

	}

	public static void dfs(int number, int depth) {
		if (depth == 5 || flag) {
			flag = true;
			return;
		}

		visited[number] = true;

		for (int target : graph.get(number)) {
			if (!visited[target]) {
				dfs(target, depth + 1);
			}
		}

		visited[number] = false;
	}

}

 

후기

바로 이해하지 못해서 많이 틀렸다...