[백준 13023] ABCDE (자바)

백준 13023번 ABCDE (자바)

 

 

 

출처

www.acmicpc.net/problem/13023

13023번: ABCDE

 

 

 

문제

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을 출력한다.

 

 

 

입출력 예

입출력 예 1

 

 

 

접근 방법

간단한 DFS 문제다.

문제에서 조어진 조건대로 친구 관계가 이어져야 하는데 꼬리물기를 통해 해결할 수 있다.

나는 인접리스트를 만들어 각 친구마다 가능한 관계를 모두 담았다.

 

예를 들어, 1 -> 3이고 3 -> 2 관계가 성립해야 할 때 먼저 1번이 3번과 관계를 이을 것이다.

이후에, 3을 관계를 받는 친구에서 관계를 구하는 친구로 변경하여 2번을 찾아 관계를 잇는 것이다.

 

DFS메서드에서 모든 관계가 성립할 때는 return을 두어 빠르게 메서드를 탈출할 수 있도록 하자.

 

 

내 코드

 

 

 

고려할 점

1. DFS를 사용할 것

2. 주어진 관계를 성립하는 경우 바로 1을 반환할 것