백준 22860번 폴더 정리(small) 문제 풀이(Python, 구현, DFS, Hash, Gold 3)

백준 22860번 폴더 정리(small) 문제 바로가기

문제 접근

이 문제는 되게 복잡해 보이지만 단순하게 보면 입력에서 주어지는 값들을 토대로 트리 구조를 만들고, 여러 개의 쿼리문에 대한 출력으로 해당 폴더 하위에 존재하는 모든 파일들의 종류과 개수를 출력하면 되는 문제이다.
따라서 총 두개의 부분으로 문제를 나누었는데
1. 입력에서 주어지는 값들을 토대로 트리 구조를 만들기
2. 해당 폴더 하위에 존재하는 모든 파일들의 종류과 개수를 구하기

문제 해결

입력값을 트리 구조로 구현하기

이 부분은 굉장히 간단하게 구현할 수 있었다.
dict를 이용하여 key => 상위 폴더, value => 하위 폴더 혹은 하위 파일 등등 으로 구성하면 되었다.
만약 key가 존재하지 않는다면 초기화만 해주면 되었다.

for i in range(N + M):
    P, F, C = map(str, sys.stdin.readline().split())
    if P not in dic:
        dic[P] = []
    if C=='1' and F not in dic:
        dic[F] = []

    dic[P].append(F)

폴더 하위에 존재하는 모든 파일들의 종류과 개수를 구하기

이 부분은 DFS로 찾아주었다. 사실 처음에는 재귀를 사용하여 DFS를 구현했는데 재귀오류가 나는 바람에 30분동안 헤맸다.. 결국 반복문을 사용한 DFS구현으로 해결했다. 중복제거는 set으로 해결했고 파일의 개수는 num을 사용하여 개수를 세어주어 출력하도록 했다.

def find_file(start_path):
    global num
    stack = [start_path]
    while stack:
        cur_path = stack.pop()
        for i in dic.get(cur_path):
            if i in dic:
                stack.append(i)
            if i not in dic:
                file_list.add(i)
                num += 1
    return

제출 코드

import sys
N, M = map(int, sys.stdin.readline().split())
dic = dict()

def find_file(start_path):
    global num
    stack = [start_path]
    while stack:
        cur_path = stack.pop()
        for i in dic.get(cur_path):
            if i in dic:
                stack.append(i)
            if i not in dic:
                file_list.add(i)
                num += 1
    return

for i in range(N + M):
    P, F, C = map(str, sys.stdin.readline().split())
    if P not in dic:
        dic[P] = []
    if C=='1' and F not in dic:
        dic[F] = []

    dic[P].append(F)

Q = int(sys.stdin.readline())
for i in range(Q):
    visited = []
    file_list = set()
    num = 0
    path = list(map(str, sys.stdin.readline().rstrip().split('/')))
    find_file(path[-1])
    print(len(file_list), num)