[백준] 폴더 정리(small)

 

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

22860번: 폴더 정리 (small)

DFS와 SET을 활용하여 풀 수 있는 문제입니다. 현재 폴더의 하위에 폴더를 만난 경우에는 하위 폴더로 탐색을 시작하게 되고 탐색이 끝나면 하위 폴더들 밑에 있는 파일의 종류와 숫자를 리턴으로 받게 됩니다. 파일의 개수는 더해주고 파일의 종류는 SET이므로 현재 폴더 종류에 합집합을 통해 합치게 됩니다. 파일의 종류는 파일 이름이 다르면 같은 파일 다르면 다른 파일로 취급하므로 SET을 사용하면 적절합니다.

 

import sys
from collections import defaultdict
sys.setrecursionlimit(10**9)

# sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

graph = defaultdict(list)
info = defaultdict(tuple)

# n: 폴더의 총 개수, m: 파일의 총 개수
n, m = tuple(map(int, input().split()))

# main 폴더에 대한 정보
for _ in range(n + m):
    parent, child, isFolder = tuple(map(str,input().split()))
    graph[parent].append((child, int(isFolder)))


def dfs(cur_path):
    # 파일의 개수
    file_cnt = 0
    # 파일의 종류
    file_set = set()

    # 현재 디렉토리 명
    cur = cur_path.split('/')[-1]

    for name, isFolder in graph[cur]:
        # 하위에 있는 것이 폴더인 경우
        if isFolder:
            child_file_set, child_file_cnt = dfs(cur_path + '/' + name)
            file_cnt += child_file_cnt

            # 하위 폴더의 파일셋 추가
            file_set = file_set.union(child_file_set)
        # 하위에 있는 것이 파일인 경우
        else:
            file_set.add(name)
            file_cnt += 1
    # 현재 폴더에 대한 정보 저장
    info[cur_path] = (len(file_set), file_cnt)

    # 현재 폴더에 대한 개수 추가
    return (file_set, file_cnt)

dfs('main')

q = int(input())
for _ in range(q):
    dir_name = input().rstrip()
    print(*info[dir_name])