사용 알고리즘: dfs
사용 언어: java
대체 문제가 뭔지 싶었다.
5개 관계가 일렬로 이어진 관계를 찾으라는 것
그리고 그러한 관계가 하나라도 있으면 1을 출력. 즉, 찾으면 멈춰라
package ssafyAlgorithm;
import java.io.*;
import java.util.*;
public class Main_bj_13023_ABCDE {
static int n, m, ans;
static ArrayList<Integer>[] al;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt(); //사람 수(0부터 시작)
m = sc.nextInt(); //한 그룹에 m명
al = new ArrayList[n];
for (int i = 0; i < n; i++) {
al[i] = new ArrayList<>();
}
for (int i = 0; i < m; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
al[a].add(b);
al[b].add(a);
}
//입력 끝
for (int i = 0; i < n; i++) {
boolean[] visit = new boolean[n];
visit[i] = true;
dfs_abcde(i, 1, visit);
if(ans > 0) break;
}
if(ans > 0) System.out.println(1);
else System.out.println(0);
}
private static void dfs_abcde(int node, int dept, boolean[] visit) {
if(dept == 5) {
ans++;
return;
}
for(int nxt : al[node]) {
if(!visit[nxt]) {
visit[nxt] = true;
dfs_abcde(nxt, dept+1, visit);
visit[nxt] = false;
}
}
}
}
'알고리즘 > 백준' 카테고리의 다른 글
1697_숨바꼭질 * (맞았는데 다시 풀면 또 틀리려나;) (0) | 2024.08.22 |
---|---|
15683_감시 (0) | 2024.08.20 |
1753_최단경로 (0) | 2024.08.20 |
1068_트리 (0) | 2024.08.14 |
20166_문자열 지옥에 빠진 호석 (1) | 2024.08.12 |