문제 풀이 날짜: 2023.08.31
포스트 작성일: 2023.08.31
* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.
문제 출처
백준 온라인 저지 13023번: ABCDE (골드5)
키워드
DFS, 그래프 탐색
풀이 접근법
- A, B, C, D, E 라는 문자에 집중하기보다는, 그래프에서 연달아 4개 이상의 경로가 연결되어 있는지를 확인하면 된다. 즉, DFS의 depth가 4 이상이 되면 된다.
- 44%에서 틀렸습니다를 받은 적 있는데, 실패한 경로에 대한 탐색 기록 삭제하는 작업을 해주어야 한다. 이미 간 경로가 유망하지 않을 때, visited 표시를 복구해주어야 한다.
- 그런데 이렇게 원복 해주면 방문했던 점을 재방문해서 시간 초과가 난다.
- 따라서 이전 경로가 유망하지 않을 때만(false를 반환했을 때만) visited를 되돌려주고, 그렇지 않을 때는 그대로 둔다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static List<Integer>[] graph;
private static boolean[] visited;
private static int flag = 0;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] temp = br.readLine().split(" ");
int N = Integer.parseInt(temp[0]);
int M = Integer.parseInt(temp[1]);
int[] from = {0, 1, 2, 3};
int[] to = {1, 2, 3, 4};
graph = new ArrayList[N];
visited = new boolean[N];
for(int i = 0; i < N; i++) {
graph[i] = new ArrayList<>();
}
for(int i = 0; i < M; i++) {
temp = br.readLine().split(" ");
int v = Integer.parseInt(temp[0]);
int u = Integer.parseInt(temp[1]);
graph[v].add(u);
graph[u].add(v);
}
for(int i = 0; i < N; i++) {
visited[i] = true;
DFS(i, 0);
visited = new boolean[N];
}
System.out.println(flag);
}
private static boolean DFS(int start, int depth) {
if(depth >= 4) {
flag = 1;
return true;
}
for(int u : graph[start]) {
if(!visited[u]) {
visited[u] = true;
if(!DFS(u, depth + 1)) {
visited[u] = false;
}
}
}
return false;
}
}
git 링크
https://github.com/jinju9553/23-CodingTest/blob/d37c971dcff078a725f78a2ce49db2b02ecde004/%EB%B0%B1%EC%A4%80/Gold/13023.%E2%80%85ABCDE/ABCDE.java
'Study > Problem Solving' 카테고리의 다른 글
[백준 / Java] 16401번: 과자 나눠주기 (실버2) (0) | 2023.09.11 |
---|---|
[백준 / Java] 15683번: 감시 (골드4) (0) | 2023.09.11 |
[SWEA / Java] 1767번: 프로세서 연결하기 (0) | 2023.08.30 |
[백준 / Java] 17070번: 파이프 옮기기 1 (골드5) (0) | 2023.08.30 |
[백준 / Java] 1600번: 말이 되고픈 원숭이 (골드3) (2) | 2023.08.30 |