[백준] 31406 - 트리 탐색기 (Easy)

[문제]

---

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

[풀이]

---

입력 부분을 보니 폴더 N와 명령 Q가 각각 2,000보다 작거나 같기 때문에
별 짓을 다 해도 시간초과는 안날 것 같았다.

move를 dfs로 하려고 했으나.. 더 복잡할 것 같아 다른 방법을 사용했다.

DFS 로 탐색한 결과를 order에 저장한다. 예제 1 로 따지면 [1, 2, 6, 4, 3, 5]가 된다.
toggle 을 하면 그 폴더만 toggle을 해준다.

move k 명령에서

• k가 음의 정수가 아닐 때
  order 순서대로 가다가 toggle이 안된 폴더를 만나면 그 폴더보다 깊은 폴더는 카운트를 무시한다.
  다만, toggle이 안된 폴더와 깊이가 같은 폴더를 만나면 d를 초기화하고 다시 진행한다.

• k가 음의 정수일 때
  맨 위에서 현재 폴더의 위치까지 몇 번 내려가야 하는지 구한 값과 k를 이용하여
  다시 맨 위에서부터 내려온다.

[코드]

---

import sys
sys.setrecursionlimit(10**4)
r=sys.stdin.readline

N,Q=map(int,r().split())

graph = [[] for _ in range(N+1)]
toggle = [0]*(N+1)
toggle[1]=1

depth = [0]*(N+1)
order=[]
def dfs(n, d):
    order.append(n)
    depth[n] = d
    for e in graph[n]:
        dfs(e, d+1)

for i in range(1,N+1):
    a = list(map(int,r().split()))
    if a[0] == 0: continue
    for j in range(a[0]):
        graph[i].append(a[j+1])

dfs(1, 0)

def forward(k, cursor):
    i=0
    d=2001
    tmpCursor = cursor
    while i < k:
        if tmpCursor == N-1: break
        if not toggle[order[tmpCursor]] and d==2001:
            d = depth[order[tmpCursor]]
        tmpCursor += 1
        if depth[order[tmpCursor]] > d:
            continue
        d = 2001
        i+=1
        cursor = tmpCursor
    return cursor

def getLocFromTop(target):
    loc=0
    d=2001
    tmpCursor = 1
    while order[tmpCursor] != target:
        if not toggle[order[tmpCursor]] and d==2001:
            d = depth[order[tmpCursor]]
        tmpCursor += 1
        if depth[order[tmpCursor]] > d:
            continue
        d = 2001
        loc+=1
    return loc

cursor = 1
for _ in range(Q):
    cmd = r().split()

    if cmd[0] == "toggle":
        toggle[order[cursor]] = not toggle[order[cursor]]
    else:
        k = int(cmd[1])
        if k >= 0:
            cursor = forward(k, cursor)
        else:
            k*=-1
            loc = getLocFromTop(order[cursor])
            cursor = forward(loc-k, 1)
        print(order[cursor])