- BFS 탐색을 실제로 활용하는 문제를 하나 풀었다.
나 스스로는 재귀 호출 쪽으로 생각해보다가 풀지 못했던 문제이다. “너무 경우의 수가 많을 것 같은, 말하자면 재귀로 돌려야 할 것 같은데 분기가 너무 많아지는 것 같다 싶은 문제인 경우, 모든 경우의 수를 다 나열해야겠구나싶은 경우”에 BFS를 사용하면 된다고 한다..! 주어진 트리나 그래프의 자료 정보가 없는데 어떻게 가능했던 건지는, 이전에 한 번 적어봤던 BFS 탐색 코드와 비교해가며 좀 더 연구해봐야겠다.
- DFS에는 스택! BFS에는 큐!
- 파이썬에서 스택은 list로 쓰고, 파이썬에서 큐는 collections.deque을 쓰고, 파이썬에서 최소힙(과 최대힙)은 heapq로 구현되어 있는 걸 쓰면 된다.
어제 저녁까지 고민하던 문제(’영화관 좌석 배정하기’)의 마지막 한 조각(’VIP’석을 어떻게 고정시킬 것인가)을 마침내 완성시켰다! 원래의 재귀 호출 3분기에 VIP 조건 2가지를 추가한 부분은 내가 생각해도 아교처럼 요리조리 참 잘 엮어냈다 싶다. 되는대로 작동만 하게 한 게 아니라 로직이 빈틈없도록 만들었다. 암. 이건 칭찬할 만 하지. 시간 복잡도까지 생각하지는 않았지만. 제출한 코드가 너무 아름다워서 스파르타 분들이 감격해 쓰러질지도 모르겠다. 오랜만의 성취감으로 점심 때까지 배가 빵빵하게 불렀다.
( 해당 문제 깃헙 링크(주석을 남겨둔 버전) : https://github.com/devocean-han/Algorithm-Practice/blob/master/week_4/10_homework_theatre_seats.py )
Uploaded by N2T