백준 22860번 : 폴더 정리(small)

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

22860번: 폴더 정리 (small)

아이디어

최근 본 코딩테스트에서 거의 똑같은 문제가 나왔었다.

근데 또 문제 잘못 읽음...ㅎㅎ 출력 순서를 반대로 했었다.

위상정렬 아이디어를 사용했다.

folder_dict에서 각 key에 해당하는 value는 길이가 3인 리스트로 구성되어있다.

0번 인덱스는 해당 폴더의 상위 폴더 리스트, 1번 인덱스는 해당 폴더 하위에 있는 파일들, 2번 인덱스는 해당 폴더 아래에 있는 폴더 개수이다.

 

import sys
from collections import deque
input = sys.stdin.readline

n,m = map(int,input().rstrip().split())

folder_dict = dict()
folder_dict['main'] = [[],[],0]

for _ in range(n+m):
    A,B,f = input().rstrip().split()
    f = int(f)
    if A not in folder_dict.keys():
        folder_dict[A] = [[],[],0]

    if f == 0:
        folder_dict[A][1].append(B)
    else:
        if B in folder_dict.keys():
            folder_dict[B][0].append(A)
            folder_dict[A][2] += 1
        else:
            folder_dict[B] = [[A],[],0]
            folder_dict[A][2] += 1

for f in folder_dict.keys():
    folder_dict[f][1] = list(set(folder_dict[f][1]))
    if f != 'main' and len(folder_dict[f][0]) == 0:
        folder_dict[f][0].append('main')

queue = deque([])

for f in folder_dict.keys():
    if folder_dict[f][2] == 0:
        queue.append(f)

while queue:
    nowf = queue.popleft()

    for nextf in folder_dict[nowf][0]:
        folder_dict[nextf][1] += folder_dict[nowf][1]
        folder_dict[nextf][2] -= 1
        if folder_dict[nextf][2] == 0:
            queue.append(nextf)

n = int(input().rstrip())

for _ in range(n):
    ask = list(input().rstrip().split('/'))
    if ask[-1] in folder_dict.keys():
        temp = folder_dict[ask[-1]][1]
        temp = set(temp)
        print(len(temp),len(folder_dict[ask[-1]][1]))
    else:
        print(0,0)