BOJ
[ 백준 16964 ] - DFS 스페셜 저지(Java)
dongx._.2
2023. 2. 4. 19:38
16964번: DFS 스페셜 저지
첫째 줄에 정점의 수 N(2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에는 트리의 간선 정보가 주어진다. 마지막 줄에는 DFS 방문 순서가 주어진다. DFS 방문 순서는 항상 N개의 정수로 이루
www.acmicpc.net
문제 이해 & 기본 개념
- 그래프와 방문 순서가 주어진다.
- 해당 그래프에서 입력받은 순서가 dfs로 방문 가능한지를 체크하는 문제
- 해당 문제는 방문 순서에 대한 기준을 두지 않았다.
- 즉, 어떤 순서로 방문을 해도 dfs로 방문 가능한 순서이기만 하면 된다.
중요 포인트
- n이 10만까지 들어오므로, dfs를 완전히 수행하면 시간 초과
- dfs로 접근하되, 수행 시간을 줄여아한다.
최종 풀이
- dfs의 경우 여러 자식들 중 어떤 자식을 먼저 방문하냐에 따라 방문 순서가 달라진다.
- 해당 문제에서는 현재 노드의 자식들 모두에 대해 방문해야할 노드가 있는지 체크한 후 방문하면 된다.
- 현재 노드의 자식들을 HashSet에 저장한다. (부모는 제외, 양방향 그래프이므로 자식 리스트에 부모도 같이 존재)
- 만약 현재 노드가 Leaf라면 (자식이 없는 경우, set의 크기가 0) return
- 다음 방문 순서의 노드가 현재 노드의 자식이고, 방문하지 않았다면 재귀를 통해 해당 노드를 방문한다.
- 현재 노드의 모든 자식 수만큼 반복 (예시 참조)
- 해당 그래프에서 1-3-5-8로 방문했을 경우, 다시 3번에서 2번과 6번을 방문해야한다.
- 즉, 한 노드에선 무조건 자식 갯수만큼은 방문을 하게 됨
- 따라서, 아래와 같이 len(자식의 개수)만큼 반복문을 통해 노드를 방문한다.
- 만약 아래의 dfs에서 해당 노드의 자식을 방문하고 돌아왔다면, 그 노드는 건너뛸 수 있게 된다.
// 현재 노드의 자식들을 통해서 다음 order로 갈 수 있는지만 체크하는 반복문
while(len > 0){
int next = order[idx];
// 현재 노드에서 다음 order로 갈 수 있는 자식이 있으면 dfs 진입
if(!node[next].visited_ && set.contains(next)){
idx++;
node[next].visited_ = true;
dfs(curNode, next);
len--;
}
else break; // 없으면 바로 종료
}주의 할 점
- 해당 문제에선 양방향 그래프가 들어온다.
- 단방향 그래프라고 생각하고 풀면 틀릴 수 있다.
소스 코드
class Node{
boolean visited_ = false;
HashSet<Integer> child = new HashSet<>();
}
public class Main {
public static Node[] node;
public static int[] order;
public static int n, idx = 1;
public static void dfs(int parent, int curNode){
HashSet<Integer> set = new HashSet<>();
for (Integer i : node[curNode].child) if(i != parent) set.add(i);
int len = set.size();
if(len == 0) return;
// 현재 노드의 자식들을 통해서 다음 order로 갈 수 있는지만 체크하는 반복문
while(len > 0){
int next = order[idx];
// 현재 노드에서 다음 order로 갈 수 있는 자식이 있으면 dfs 진입
if(!node[next].visited_ && set.contains(next)){
idx++;
node[next].visited_ = true;
dfs(curNode, next);
len--;
}
else break; // 없으면 바로 종료
}
}
public static void main(String[] args) throws IOException {
// TODO code application logic here
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
n = Integer.parseInt(br.readLine());
node = new Node[n + 1];
for (int i = 0; i < n+1; i++) node[i] = new Node();
for (int i = 0; i < n - 1; i++) {
st = new StringTokenizer(br.readLine());
int n1 = Integer.parseInt(st.nextToken());
int n2 = Integer.parseInt(st.nextToken());
if(!node[n1].child.contains(n2)) {
node[n1].child.add(n2);
node[n2].child.add(n1);
}
}
String[] input = br.readLine().split(" ");
order = new int[n];
for(int i = 0; i < input.length; i++)
order[i] = Integer.parseInt(input[i]);
if(order[0] == 1){
node[1].visited_ = true;
dfs(-1, 1);
}
System.out.println((idx == n ? 1 : 0));
}
}
시도 방법 1 (35% 시간 초과)
- 스택을 이용하여 방문하는 모든 경로를 체크했다.
- 이전 경로를 기록하고 더 이상 갈 수 없으면 다시 돌아가는 방법ㅋ
- 시간 초과 안나는게 이상한 코드였다.
class Node{
int index_;
boolean visited_ = false;
ArrayList<Integer> child = new ArrayList<>();
public Node(int index_) {
this.index_ = index_;
}
}
public class Main {
public static Node[] node;
public static int n;
public static boolean isCorrectOrder(int[] order, int n){
if(order[0] != 1) return false;
node[1].visited_ = true;
int index = 1;
int cur = 1; // 현재 방문 중인 노드
Stack<Integer> prevStack = new Stack();
while(index < n){
// 다음 노드가 현재 노드와 연결되어 있고 방문하지 않은 노드인 경우
int next = order[index];
if(node[cur].child.contains(next) && !node[next].visited_) {
prevStack.push(cur); // 다음 노드로 이동
node[cur = next].visited_ = true;
index++;
}
else {
/**
* else에 들어오면 현재 노드에서 다음 노드로 갈 수 없다는 소린데,
* stack이 비어있으면 더 올라갈 수도 없다는 뜻이므로 올바른 순서가 아님
*/
if(prevStack.isEmpty()) return false;
while(!node[cur].child.contains(order[index]) && !prevStack.isEmpty()){
cur = prevStack.pop();
}
}
}
return true;
}
public static void main(String[] args) throws IOException {
// TODO code application logic here
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
n = Integer.parseInt(br.readLine());
node = new Node[n + 1];
for (int i = 0; i < n + 1; i++) node[i] = new Node(i);
for (int i = 0; i < n - 1; i++) {
st = new StringTokenizer(br.readLine());
int n1 = Integer.parseInt(st.nextToken());
int n2 = Integer.parseInt(st.nextToken());
if(!node[n1].child.contains(n2)) {
node[n1].child.add(n2);
node[n2].child.add(n1);
}
}
String[] input = br.readLine().split(" ");
int[] order = new int[n];
for(int i = 0; i < input.length; i++){
order[i] = Integer.parseInt(input[i]);
}
if(isCorrectOrder(order, n)) System.out.println("1");
else System.out.println("0");
}
}
시도 방법 2 (72% 시간 초과)
- Depth를 통해 올바른 순서인지 판단하는 방법을 시도해봤다.
- dfs를 한 번 수행하여 노드들의 depth를 체크하고, 방문 순서에서 depth가 이어지지 않으면 해당 노드의 자식이 있는지 확인한다.
- 자식이 있다면, 끝까지 이어지지 않은 것이므로 올바르지 않은 순서
=> 여전히 dfs를 한 번은 수행하므로 시간 초과
class Node{
int depth = 0;
boolean visited_ = false;
ArrayList<Integer> child = new ArrayList<>();
}
public class Main {
public static Node[] node;
public static int n;
public static void dfs(int idx, int depth){
if(node[idx].visited_) return;
node[idx].depth = depth;
node[idx].visited_ = true;
for (Integer child : node[idx].child){
if(!node[child].visited_) dfs(child, depth + 1);
}
}
public static boolean isCorrectOrder(int[] order){
if(order[0] != 1) return false;
dfs(1, 1);
for (int i = 0; i < order.length-1; i++) {
int curDepth = node[order[i]].depth;
int nextDepth = node[order[i+1]].depth;
if(curDepth != 0 && curDepth+1 != nextDepth){
// 양방향 그래프이므로 자신보다 깊은 노드가 있는지 확인
for (Integer child : node[order[i]].child) {
if(curDepth < node[child].depth) return false;
}
}
}
int lastDepth = node[order[order.length-1]].depth;
for (Integer child : node[order[order.length-1]].child) {
if (lastDepth < node[child].depth) return false;
}
return true;
}
public static void main(String[] args) throws IOException {
// TODO code application logic here
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
n = Integer.parseInt(br.readLine());
node = new Node[n + 1];
for (int i = 0; i < n+1; i++) node[i] = new Node();
for (int i = 0; i < n - 1; i++) {
st = new StringTokenizer(br.readLine());
int n1 = Integer.parseInt(st.nextToken());
int n2 = Integer.parseInt(st.nextToken());
if(!node[n1].child.contains(n2)) {
node[n1].child.add(n2);
node[n2].child.add(n1);
}
}
String[] input = br.readLine().split(" ");
int[] order = new int[n];
for(int i = 0; i < input.length; i++)
order[i] = Integer.parseInt(input[i]);
if(isCorrectOrder(order)) System.out.println("1");
else System.out.println("0");
}
}