16964 DFS 스페셜 저지

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

문제

BOJ에서 정답이 여러가지인 경우에는 스페셜 저지를 사용한다. 스페셜 저지는 유저가 출력한 답을 검증하는 코드를 통해서 정답 유무를 결정하는 방식이다. 오늘은 스페셜 저지 코드를 하나 만들어보려고 한다.

정점의 개수가 N이고, 정점에 1부터 N까지 번호가 매겨져있는 양방향 그래프가 있을 때, DFS 알고리즘은 다음과 같은 형태로 이루어져 있다.

 

이 문제에서 시작 정점은 1이기 때문에 가장 처음에 호출하는 함수는 dfs(1)이다. DFS 방문 순서는 dfs함수에서 // x를 방문 이라고 적힌 곳에 도착한 정점 번호를 순서대로 나열한 것이다.

트리가 주어졌을 때, 올바른 DFS 방문 순서인지 구해보자.

입력

첫째 줄에 정점의 수 N(2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에는 트리의 간선 정보가 주어진다. 마지막 줄에는 DFS 방문 순서가 주어진다. DFS 방문 순서는 항상 N개의 정수로 이루어져 있으며, 1부터 N까지 자연수가 한 번씩 등장한다.

출력

입력으로 주어진 DFS 방문 순서가 올바른 순서면 1, 아니면 0을 출력한다.

=========

문제 설명

DFS는 현재 정점으로부터 이동할 수 있는 정점으로 가능한 한 쭉 이동하는 알고리즘이다. 

정점 1이 2,3과 연결되어 있고 2는 4와 연결되어 있다면 DFS시 나올 수 있는 경로는 

1 -2 -4  또는 1- 3 이다. 

나올 수 있는 경로는 1-2-4-3 또는 1-3-2-4 이다. 

오답 노트

 처음에는 q 를 하나 두고 갈라지는 정점이 생길 때마다 자식들을 모두 q에 unshift를 하는 것으로 앞에 끼워준 뒤 입력 맨 마지막 줄과 비교하는 것으로 다음 경로를 찾아주었다. 하지만 이럴 경우 q에 너무 많은 요소가 들어가서인지 제출 시 73%에서 메모리 초과가 발생했다.

조금 더 간소화 된 방법이 없을까 생각해본 결과 그래프의 각 정점 별로 우선순위를 둬서 그 우선순위에 맞춰 DFS 방식으로 방문하면 된다는 것을 떠올렸다. 즉 입력 맨 마지막 줄이 1 3 2 4 라면 각 정점의 우선순위는 

1=>0

2=>2

3=>1

4=>3 이 된다.

(인덱스를 우선순위로) 

위의 우선순위를 바탕으로 그래프를 정렬한다면 코드는 아래와 같다.

const gr = Array.from({ length: n + 1 }, () => []);
const checkArray = input
        .at(-1)
        .split(' ')
        .map((c) => +c);

for (let i = 1; i < input.length - 1; i++) {
    const [s, e] = input[i].split(' ').map((v) => +v);
    gr[s].push(e);
    gr[e].push(s);
}

gr.forEach((r) =>
    r.sort((a, b) => checkArray.indexOf(a) - checkArray.indexOf(b))
);

이제 여기서 구한 gr을 바탕으로 정점 1부터 DFS 탐색을 시작한다.

이때 전역으로 result =[1] 를 선언하여 방문하는 정점을 담아준다. (첫 정점은 1이므로 미리 result에 1 넣은 거임)   

또한 visited 를 선언하여 방문 한 정점은 패스해주는 것으로 탐색 최소화 해줌

    const result = [1];
    visited[1] = true;
    const dfs = (cur) => {
        const idx = result.length;
        if (result[idx - 1] !== checkArray[idx - 1]) {
            return;
        }
        if (gr[cur].length === 0) return;

        for (const next of gr[cur]) {
            if (visited[next] === true) continue;
            visited[next] = true;
            result.push(next);
            dfs(next);
        }
    };
    dfs(1);

이미 각 정점과 연결 된 요소들은 위에서 정렬이 된 상태이므로 반복문에서 바로 dfs를 실행하더라도 방문할게 없어진다면 가장 최근에 갈라진 요소로 다시 돌아가서 방문하게 되는 거임

정답 코드

아래는 자바스크립트 코드인데 이렇게 할 경우 init에서 시간 초과가 발생한다.

그래서 파이썬으로 코드를 변경하여 제출했더니 정답이 됐다..

// 시간 초과 뜨는 자바스크립트 코드 

const init = (input) => {
    const n = +input[0];

    const gr = Array.from({ length: n + 1 }, () => []);
    const checkArray = input
        .at(-1)
        .split(' ')
        .map((c) => +c);

    for (let i = 1; i < input.length - 1; i++) {
        const [s, e] = input[i].split(' ').map((v) => +v);
        gr[s].push(e);
        gr[e].push(s);
    }

    gr.forEach((r) =>
        r.sort((a, b) => checkArray.indexOf(a) - checkArray.indexOf(b))
    );
    const visited = Array.from({ length: n + 1 }).fill(false);

    return [gr, checkArray, visited];
};

const main = (input) => {
    init(input);
    const [gr, checkArray, visited] = init(input);
    let answer = 1;
    const result = [1];
    visited[1] = true;
    const dfs = (cur) => {
        const idx = result.length;
        if (result[idx - 1] !== checkArray[idx - 1]) {
            return;
        }
        if (gr[cur].length === 0) return;

        for (const next of gr[cur]) {
            if (visited[next] === true) continue;
            visited[next] = true;
            result.push(next);
            dfs(next);
        }
    };
    dfs(1);

    if (result.length !== checkArray.length) {
        answer = 0;
    } else {
        for (let i = 0; i < result.length; i++) {
            if (result[i] !== checkArray[i]) {
                answer = 0;
                break;
            }
        }
    }
    console.log(answer);
};

const input = require('fs')
    .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
    .toString()
    .trim()
    .split('\n');
main(input);

# 정답이 되는 파이썬 코드

def main(gr, check_array, visited):
    answer = 1
    result = [1]
    visited[1] = True
    
    def dfs(cur):
        idx = len(result)
        if result[idx - 1] != check_array[idx - 1]:
            return
        if not gr[cur]:  
            return
            
        for next_node in gr[cur]:
            if visited[next_node]:
                continue
            visited[next_node] = True
            result.append(next_node)
            dfs(next_node)
    
    dfs(1)
    
    if len(result) != len(check_array):
        answer = 0
    else:
        for i in range(len(result)):
            if result[i] != check_array[i]:
                answer = 0
                break
    
    print(answer)

# 입력 처리
n = int(input())
gr = [[] for _ in range(n+1)]
for _ in range(n-1):
    start, end = map(int, input().rsplit())
    gr[start].append(end)
    gr[end].append(start)
check_array = list(map(int,input().rsplit()))

for r in gr:
        r.sort(key=lambda x: check_array.index(x))
    
visited = [False] * (n + 1)

main(gr,check_array,visited)