[백준/파이썬] #22860

30분 타임어택(정확히는 40분 걸렸다)에 성공했다! 답 안 보고 풀었다. 

 

전역 변수로 파일의 개수를 세기 위한 answer, 파일의 종류를 세기 위한 files, 경로를 탐색하기 위한 directories 변수를 선언해줬다. 

 

directories 변수가 필요했던 이유는, 주어지는 쿼리에 따라서 main 디렉토리부터 모든 경로를 탐색하는 것은 비효율적이기 때문이었다. 그랬기에 아직 쿼리에서 제시한 디렉토리가 남아있으면(directories 리스트에 원소가 남아 있으면) 해당 노드의 자식들을 전부 탐색하지 않고 바로 그 다음 디렉토리를 탐색하는 식으로 작성했다. 

import sys
from collections import defaultdict, deque

sys.setrecursionlimit(10**9)

N, M = map(int, input().split())
children = defaultdict(list)

for _ in range(N + M):
    P, F, C = input().split(" ")
    is_node_folder = True if C == "1" else False
    children[P].append((F, is_node_folder))


def search(node, is_folder):
    global directories, answer, files
    if not is_folder:
        answer += 1
        files.add(node)
        return

    if len(directories) > 0:
        next_node_name = directories.popleft()
        search(next_node_name, True)
    else:
        for child, is_child_folder in children[node]:
            search(child, is_child_folder)


def solution(path: str):
    global directories, answer, files
    answer = 0
    files.clear()
    directories = deque(path.split("/"))
    search(directories[0], True)
    print(f"{len(files)} {answer}")


answer = 0
files = set()
directories = deque([])

Q = int(input())
paths = []
for _ in range(Q):
    paths.append(input())

for path in paths:
    solution(path)