백준 13023번 <ABCDE>

백준 알고리즘 13023번

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

13023번: ABCDE

---

13023번

N명의 사람이 있고 M개의 친구관계가 주어질 때 다음과 같은 친구관계가 존재하는지 구하여라.

• A는 B와 친구
• B는 C와 친구
• C는 D와 친구
• D는 E와 친구

 

입력으로 첫 줄에 N과 M이 주어진다. 그 다음 M개의 줄에는 정수 a와 b가 주어지는데 이는 a와 b가 친구라는 뜻이다.

 

출력으로 위와 같은 친구관계가 존재한다면 1을, 존재하지 않는다면 0을 출력한다.

---

문제 해결

어려웠다,,, 쉬워보였는데 왜 이렇게 어려운지ㅠ

 

처음에는 MST를 이용해서 풀어야 하나 했는데 아닌 거 같아서 BFS를 이용해서 풀어보려고 했는데 잘 안됬다.

친구 관계를 인접 관계로 하고 DFS를 돌려서 depth가 5가 되면 된다.

 

DFS를 돌릴 때는 방문한 후에 인접 관계를 기준으로 다시 DFS를 호출하고 depth가 5가 안 됬으면 방문을 취소한다.

(다른 DFS에서 방문할 수 있도록)

---

코드

package boj13023;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	static int N;
	static ArrayList<Integer>[] list;
	static boolean[] visit;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		N = sc.nextInt();
		int M = sc.nextInt();

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

		for (int i = 0; i < M; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			list[a].add(b);
			list[b].add(a);
		} // end input

		int ans = 0;
		for (int i = 0; i < N; i++) {
			visit = new boolean[N];
			if (dfs(i, 1)) {
				ans = 1;
				break;
			}
		}
		System.out.println(ans);
	}

	static boolean dfs(int n, int depth) {
		visit[n] = true;
		if (depth == 5) {
//			System.out.println(Arrays.toString(visit));
			return true;
		}
		boolean chk = false;
		int size = list[n].size();
		for (int i = 0; i < size; i++) {
			if (visit[list[n].get(i)])
				continue;
			chk = dfs(list[n].get(i), depth + 1);
			if(chk) return true;
		}
		visit[n] = false;
		return false;
	}

}

---

결과

---

visit 체크를 재귀 호출하기 전에 하면 안된다!!ㅎ