[백준] 폴더 정리 (small)

유승선 ·2022년 7월 5일
0

백준

목록 보기
31/64

흥미로운 문제를 발견하고자 하는 내 노력으로 또 한번 백준에서 추천 문제들을 대거 찾은 후에 하나씩 도장 깨기 처럼 풀고 있는 중이다. 요즘 부쩍 들었던 생각중 하나는 시뮬레이션과 구현쪽에서 더 완벽하게 해야겠다고 생각했어서 집중적으로 풀고 있는 중이다.

문제는 처음 읽으면 솔직히 이게 뭐지 하고 이해가 안갔을거다. 일단 N 은 폴더의 숫자, 그리고 M은 파일의 총 개수를 의미하고 main 부터 시작해서 그 아래 하위 구조가 계층적으로 이어져 있다. 폴더 옆에 1 과 0의 숫자는 각각 1은 폴더를 의미 0은 파일을 의미하고 가장 밑에있는 query 를 실행 했을때 main/FolderA 의 뜻은 main 폴더를 타고 가서 FolderA에 갔을때 어떤 파일 혹은 폴더가 있는 지를 찾았어야했다. 결과적으로 리턴해야 하는 부분은 파일의 종류와 개수이다.

먼저 이 문제를 봤을때 단순한 구현과, 문자열을 이용한 시뮬레이션인가 하고 생각했지만 자세히 읽어본 결과 이 문제는 그래프 문제와 정말 유사하다. 다만 내가 보통 그래프를 2D 벡터 형식으로 항상 만들어 왔다면 이 문제는 그래프를 Map 형식으로 만들어야 풀 수 있다는 결론이 나왔었다.

즉, Map에 key 를 폴더 이름으로 하고 그 하위 폴더들을 pair<string,int> 형식으로 해서 세팅을 해야지 탐색하기 훨씬 편했단 것이다.

여러가지 함수를 썼고, 하나씩 설명을 할것이다.

가장 처음에 removeSlash 같은 경우는 query 파트로 넘어갔을때 main/FolderA ... 이 구조에서 / 표시를 없애기 위해서 적었다.

이 부분을 없앤 이유는 결국 파일을 타고 들어갈때 가장 마지막에 있는 파일 부분만 탐색하면 됐기때문에 parsing 이 가장 먼저 필요하다고 생각했기 때문이다. '/' 를 없애고 난 후에는 stringstream 을 이용해서 나누어줬다.

이제 파일의 마지막 경로를 구할수 있으니 바로 dfs()에 마지막 경로를 입력해서 탐색을 시작해준다.

굉장히 단순한 dfs 함수다. 파일명에 있는 pair 을 확인후에 1(폴더) 면은 재귀를 해주고 0(파일) 이면 check라는 또 다른 맵에다가 표시를 해준다.

dfs 탐색이 끝난 후에는 업데이트 했던 맵을 기준으로 몇종류가 있었는지, 또 몇개의 파일이 있었는지를 쉽게 구할수있다.

물론 매번 탐색이 끝날때마다 checked map을 초기화 하는거를 잊지말아야한다.

오랜만에 다른 무리 없이 한번에 통과 했던 코드라서 기분이 좋았다. 앞으로도 이런 코드를 쓸수있으면 좋겠다.

배운점:
1. String 과 DFS 활용.
2. 문제 이해하는 법.

profile
성장하는 사람

0개의 댓글