[백준/자바] 13023 ABCDE 친구 관계 파악하기

[백준/자바] 13023 친구 관계 파악하기

 

 

📌 문제 

BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다.

오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다.

A는 B와 친구다.B는 C와 친구다.C는 D와 친구다.D는 E와 친구다.

위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오.

 

 

⚔ 입력

첫째 줄에 사람의 수 N (5 ≤ N ≤ 2000)과 친구 관계의 수 M (1 ≤ M ≤ 2000)이 주어진다.

둘째 줄부터 M개의 줄에는 정수 a와 b가 주어지며, a와 b가 친구라는 뜻이다. (0 ≤ a, b ≤ N-1, a ≠ b) 같은 친구 관계가 두 번 이상 주어지는 경우는 없다.

 

 

📣 출력

문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다.

 

 

 

 

---

 

 

 

💎 문제분석하기

 

DFS 알고리즘으로 아이디어만 얻을 수 있으면 어렵지 않게 풀린다. 

 

결국 5 깊이까지 내려간다면 1을 출력하고 아니면 0을 출력하면 된다. 

 

문제의 예시를 바탕으로 손으로 작성해본다면 다음과 같다. 

 

 

 

 

 

 

 

 

💡 코드 구현하기

 

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

public class Main {

	private static boolean[] visistedDfs;
	private static ArrayList<Integer>[] adjacentNodes;
	private static boolean satisfyingAssignedDepth;

	public static void main(String[] args) {
		int N;    // 주어지는 사람의 수 = node
		int M;    // 주어지는 관계의 수 = edge
		satisfyingAssignedDepth = false;
		Scanner sc = new Scanner(System.in);

		N = sc.nextInt();
		M = sc.nextInt();
		adjacentNodes = new ArrayList[N];
		visistedDfs = new boolean[N];

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

		for (int i = 0; i < M; i++) {
			int node1 = sc.nextInt();
			int node2 = sc.nextInt();
			adjacentNodes[node1].add(node2);
			adjacentNodes[node2].add(node1);
		}

		for (int i = 0; i < N; i++) {
			dfs(i, 1);					// depth 1부터 시작하도록 설정
			if (satisfyingAssignedDepth) {
				break;
			}
		}

		if (satisfyingAssignedDepth) {
			System.out.println("1");
		} else {
			System.out.println("0");
		}
	}

	private static void dfs(int now, int depth) {
		if (depth == 5) {
			satisfyingAssignedDepth = true;
			return;
		}
		visistedDfs[now] = true;

		for (int i : adjacentNodes[now]) {
			if (!visistedDfs[i]) {
				dfs(i, depth + 1);
			}
		}
		visistedDfs[now] = false;
	}
}

 

 

 

 

 

 

 

 

 

---

 

 

 

풀이 참고 : Do it! 알고리즘 코딩테스트 - 자바 편