[문제 링크]
https://www.acmicpc.net/problem/13023
[난이도]
- Gold 5
[알고리즘]
- 백트래킹
[코드]
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main {
static int N, M;
static ArrayList<ArrayList<Integer>> adj;
static boolean[] visited;
static boolean found = false;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
adj = new ArrayList<>();
for (int i = 0; i < N; i++) {
adj.add(new ArrayList<>()); // 정점의 수만큼 생성
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
adj.get(a).add(b); // 양방향 간선
adj.get(b).add(a); // 양방향 간선
}
visited = new boolean[N];
for (int i = 0; i < N; i++) {
if (!found) { // ABCDE가 존재하면 true 발견하지 못했다면 false
dfs(i, 0);
}
}
System.out.println(found ? 1 : 0);
}
static void dfs(int node, int depth) {
if (depth == 4) { // depth가 4면 ABCDE가 서로 연결되어있다는 뜻
found = true;
return;
}
visited[node] = true;
for (int next : adj.get(node)) {
if (!visited[next]) { // 중복방문을 방지
dfs(next, depth + 1);
if (found) return;
}
}
visited[node] = false; // 완전탐색을위해 다시 false로 변경
}
}[풀이]
이중 ArrayList로 인정리스트인 Adjacency list를 선언해준후.
각 정점을 기준으로 dfs를 반복해 depth가 4인경우를 찾아준다.
depth가 4일경우 ABCDE가 친구인 경우이다.
찾았다면 1을 못찾았다면 0을 출력한다.
'코딩테스트' 카테고리의 다른 글
| 백준 2529 : 부등호 [JAVA] (0) | 2024.06.21 |
|---|---|
| 백준 2023 : 신기한 소수 [JAVA] (0) | 2024.06.20 |
| 백준 2573 : 빙산 [JAVA] (0) | 2024.06.18 |
| 백준 13549 : 숨바꼭질 3 [JAVA] (0) | 2024.06.15 |
| 백준 2589 : 보물섬 [JAVA] (0) | 2024.06.15 |
