골드 4인데도 막힌...

#16964 DFS 스페셜 저지 https://www.acmicpc.net/problem/16964

16964번: DFS 스페셜 저지

 

처음 내가 구현했던 코드이다.

import sys
input = sys.stdin.readline
N = int(input())
matrix = [[] for _ in range(N+1)]
for i in range(N-1):
    prev, to = map(int, input().split())
    matrix[prev].append(to)
    matrix[to].append(prev)
matrix[0].append(1)
target = list(map(int, input().split()))

# for i in range(N+1):
#     print(i, matrix[i])

stack = [0]
for x in target:
    if x in matrix[stack[-1]]:
        stack.append(x)
    else:
        m = stack[-1]
        while x not in matrix[m]:
            m = stack.pop()
            if m == 0:
                print(0)
                exit()

        stack.append(x)

print(1)

DFS 탐색을 하면서 판단하게끔 구현했다.

테스트케이스만 통과하는 쓰레기코드..

 

결국에는 또 검색에 검색을 시작했찌..

import sys
input = sys.stdin.readline
N = int(input())
graph = [[] for _ in range(N+1)]
for i in range(N-1):
    prev, to = map(int, input().split())
    graph[prev].append(to)
    graph[to].append(prev)
target = list(map(int, input().split()))

visited = [False]*(N+1)
level = [False]*(N+1)
tsize = [0]*(N+1)


def dfs(node, lv):
    # 방문한 노드일 경우 종료
    if visited[node]:
        return 0

    # 방문기록
    visited[node] = True
    # 레벨 저장
    level[node] = lv
    # 사이즈 초기화
    size = 1
    # 그래프를 돌면서
    for i in range(len(graph[node])):
        next = graph[node][i]
        # 레벨 추가하기
        size += dfs(next, lv+1)
        # 재귀 호출 및
        # 사이즈 추가하기
    # 현재 노드에 사이즈 저장
    tsize[node] = size
    # 상위 노드에 사이즈 전달
    return size


# 트리가 1로 시작하지 않으면 0
if target[0] != 1:
    print("0")
    exit()
else:
    # 그래프 탐색 및 기록
    dfs(1, 0)
    # 입력받은 탐색순서 돌면서
    for i in range(1, N):
        x = target[i]
        # 사이즈가 1 -> 자식 노드가 없음 -> 무조건 다음 수는 다른 트리에 존재 -> 넘어감
        # 현재 순서 + 서브트리 사이즈 >= 전체 노드의 수 -> 런타임 에러 방지 -> 넘어감
        if tsize[x] == 1 or i + tsize[x] >= N:
            continue

        # 현재 순서 + 서브트리 사이즈 => 형제노드 or 상위노드
        next = target[i+tsize[x]]
        # 때문에, 서브트리 사이즈만큼 더한 노드에서는
        # 현재 노드보다 깊이(level)가 작거나 같아야 정상적인 트리이다.
        # 때문에, 더 큰 경우에 0을 출력하고 종료시켜준다.
        if level[next] > level[x]:
            print(0)
            exit()
    print(1)

https://blog.joonas.io/94

BOJ 16964 - DFS 스페셜 저지

 

이 블로그와

https://vixxcode.tistory.com/29

16964번 DFS 스페셜 저지 백준 파이썬

이 블로그, 총 두개의 블로그를 참고했다.

 

 

하지만 다시 구현해보라하면 자신이 없다.

휴ㅜ....