[백준 13023] ABCDE (자바)
알고리즘/백준

[백준 13023] ABCDE (자바)

반응형

백준 13023번 ABCDE (자바)

 

 

 

출처

www.acmicpc.net/problem/13023

 

13023번: ABCDE

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

www.acmicpc.net

 

 

 

문제

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을 두어 빠르게 메서드를 탈출할 수 있도록 하자.

 

 

내 코드

package dfsbfs;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class ABCDE {
/**
* 백준 13023 ABCDE (https://www.acmicpc.net/problem/13023)
*/
private static int n, m;
private static ArrayList<Integer>[] list;
private static boolean[] visit;
private static boolean exist;
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(reader.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>();
}
visit = new boolean[n];
for (int i=0; i<m; i++) {
st = new StringTokenizer(reader.readLine());
int n1 = Integer.parseInt(st.nextToken());
int n2 = Integer.parseInt(st.nextToken());
list[n1].add(n2);
list[n2].add(n1);
}
for (int i=0; i<n; i++) {
exist = false;
visit = new boolean[n];
dfs(i,0);
if (exist) {
System.out.println(1);
return;
}
}
System.out.println(0);
}
private static void dfs(int x, int count) {
if (count == 4) {
exist = true;
} else {
for (int i=0; i<list[x].size(); i++) {
if (!visit[list[x].get(i)]) {
visit[x] = true;
dfs(list[x].get(i), count+1);
if (exist) return;
visit[x] = false;
}
}
}
}
}
view raw ABCDE.java hosted with ❤ by GitHub

 

 

 

고려할 점

1. DFS를 사용할 것

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

 

반응형