백준 16964번: DFS 스페셜 저지

문제

https://www.acmicpc.net/problem/16964

16964번: DFS 스페셜 저지

---

풀이

지난 BFS 스페셜 저지 문제에 이어 정점에 1부터 n까지 번호가 매겨져 있는 양방향 그래프를 표현한 트리가 있을 때 어떤 수열이 DFS 알고리즘을 이용했을  때 해당 수열의 순서대로 방문할 수 있는지 확인하는 문제입니다. 이때 정점을 방문하는 순서는 중요하지 않습니다.

---

접근

BFS, DFS 알고리즘은 정점끼리 어떤 순서로 연결돼있는지에 따라 방문 순서가 달라집니다.

하지만 이 문제에서는 방문 방문가 먼저 나온 뒤에 이 순서대로 출력이 가능한지 확인해야 합니다.

그래서 저는 정점에 연결된 다른 정점들을 ArrayList 배열인 list로 표현했고 list[모든 정점 번호]를 주어진 수열의 순서대로 정렬한 뒤에 dfs 함수를 실행했습니다.

---

코드

자바

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main {

    static int n, cnt = 0;
    static int[] arr;
    static boolean[] visited;
    static ArrayList<Integer>[] list;

    public static void dfs(int idx) {
        if (idx != arr[cnt++]) { // (3)
            System.out.println(0);
            System.exit(0);
        }
        visited[idx] = true;
        if (list[idx] != null) { // (4)
            for (int e : list[idx]) {
                if (!visited[e]) {
                    dfs(e);
                }
            }
        }
    }

    @SuppressWarnings("unchecked")
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        visited = new boolean[n + 1];
        list = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            list[i] = new ArrayList<Integer>();
        }
        for (int i = 0; i < n - 1; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            list[x].add(y);
            list[y].add(x);
        }
        arr = new int[n];
        int[] order = new int[n + 1];
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < n; i++) { // (1)
            arr[i] = Integer.parseInt(st.nextToken());
            order[arr[i]] = i;
        }
        for (int i = 1; i <= n; i++) {
            if (list[i] != null) { // (2)
                Collections.sort(list[i], new Comparator<Integer>() {
                    @Override
                    public int compare(Integer o1, Integer o2) {
                        return order[o1] - order[o2];
                    }
                });
            }
        }
        dfs(1);
        System.out.println(1); // (5)
    }
}

(1) 그래프를 표현할 트리의 입력이 끝나면 i를 포함한 for문 안에서 수열을 순서대로 입력합니다.

이때 수열을 입력한 순서도 order[arr[i]] = i를 통해 기록해둡니다.

 

(2) 이후 i를 포함한 for문 안에서 각 정점에 연결된 다른 정점들을 수열의 순서를 기준으로 정렬합니다.

예를 들어 수열이 1 3 2 4이고 1번 정점에 순서대로 2번 정점과 3번 정점을 연결시켰다면 3번 정점보다 2번 정점을 먼저 탐색할 수 있도록 위치를 변경하는 것입니다.

이때 ArrayList를 정렬하기 위해서 Collections 클래스의 sort 메서드를 이용했는데 Comparator 객체를 compare 메서드를 수정하여 Collections.sort 메서드의 추가 인자로 사용하여 기존의 정렬 기준을 바꿨습니다.

 

모든 입력이 끝나면 탐색 시작 정점 번호가 1이기 때문에 dfs(1)을 실행합니다.

 

(3) 현재 탐색중인 정점의 번호 idx가 arr[cnt++]와 다르다면 0을 출력한 뒤에 프로그램을 종료합니다.

(2)번 과정에서 수열의 순서를 기준으로 정렬했기 때문에 값이 서로 다르다면 실패입니다.

 

(4) idx번 정점의 방문처리를 진행한 후에 p번 정점에 연결된 다른 정점이 있는지 확인합니다.

다른 정점이 있으면 foreach문을 통해 연결된 정점(e번 정점)들을 확인합니다.

e번 정점에 방문한 적이 없다면 방문처리를 해준 뒤에 dfs(e)를 재귀적으로 실행합니다.

 

(5) dfs 함수가 끝난 후에는 1을 출력한 후에 프로그램을 종료합니다.

(3)번 과정에서 프로그램이 종료되지 않았다면 문제 조건을 만족한 것이기 때문입니다.

C언어

#include <stdio.h>
#include <stdlib.h>
int n, cnt = 0, *arr, *visited, *order;
typedef struct node {
	int data;
	struct node* next;
} node;
void add(node* target, int data) {
	node* now = (node*)malloc(sizeof(node));
	now->data = data;
	now->next = target->next;
	target->next = now;
	return;
}
node* list[100001];
void dfs(int idx) {
	if (idx != arr[cnt++]) {
		printf("0");
		exit(0);
	}
	visited[idx] = 1;
	node* curr = list[idx]->next;
	while (curr != NULL) {
		if (!visited[curr->data]) {
			dfs(curr->data);
		}
		curr = curr->next;
	}
}
int compare(const void* a, const void* b) {
	int o1 = *(int*)a;
	int o2 = *(int*)b;
	return order[o1] - order[o2];
}
main() {
	scanf("%d", &n);
	visited = (int*)malloc(sizeof(int) * (n + 1));
	memset(visited, 0, sizeof(int) * (n + 1));
	for (int i = 1; i <= n; i++) {
		list[i] = (node*)malloc(sizeof(node));
		list[i]->next = NULL;
	}
	for (int i = 0; i < n - 1; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		add(list[x], y);
		add(list[y], x);
	}
	arr = (int*)malloc(sizeof(int) * n);
	order = (int*)malloc(sizeof(int) * (n + 1));
	for (int i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
		order[arr[i]] = i;
	}
	int* sorted = (int*)malloc(sizeof(int) * n);
	for (int i = 1; i <= n; i++) {
		int sortedCnt = 0;
		node* curr = list[i]->next;
		while (curr != NULL) {
			sorted[sortedCnt++] = curr->data;
			node* prev = curr;
			curr = curr->next;
			free(prev);
		}
		list[i]->next = NULL;
		qsort(sorted, sortedCnt, sizeof(int), compare);
		while (sortedCnt) {
			add(list[i], sorted[--sortedCnt]);
		}
	}
	dfs(1);
	printf("1");
}

자바를 이용한 풀이와 동일합니다. ArrayList 배열은 연결리스트를 이용하여 구현했습니다.

또한 각 정점에 연결된 다른 정점들의 순서를 정렬하기 위해 정수 배열 sorted를 따로 만들어 i를 포함한 for문에서 list[i]와 연결된 모든 값을 sorted에 넣은 후에 정렬하고 그 후에 list[i]에 순서대로 삽입했습니다.

---

결론

지난 BFS 스페셜 저지 문제에서 BFS가 아닌 DFS를 사용한다는 조건만 바뀐 문제였습니다.

마찬가지로 처음 생각했었던 DFS 알고리즘을 사용했을 때 나올 수 있는 모든 경우의 수를 수열과 비교하려고 했는데 한눈에 봐도 너무 비효율적이라고 생각하여 위와 같은 방법을 생각해냈습니다.