ok-lab

해당 문제는 DFS로 해결이 가능하다. DFS 는 깊이 우선 탐색으로, 한번에 던전을 갈 수 있는 끝까지 탐색한 후 이전 단계로 돌아가는 작업을하면 된다. 이때, 방문 여부와 방문 횟수를 초기화하고 다시 탐색을 하면 끝이다. answer = 0 def solution(k, dungeons): global answer def DFS(k, cnt, dungeons, visited): global answer answer = max(answer, cnt) # 최대 방문 횟수 for i in range(len(dungeons)): if visited[i] == 0 and k >= dungeons[i][0]: visited[i] = 1 # 방문 DFS(k-dungeons[i][1], cnt+1, dungeons,..

깊이 우선 탐색(Depth-First Search)과 너비 우선 탐색(Breadth-First Search)은 코딩 테스트에서 단골로 출제되는 문제 유형 중 하나다. 깊이 우선 탐색 (DFS, Depth-First Search) DFS는 최대한 깊이 먼저 내려간 후, 더 이상 나아갈 곳이 없는 경우에 옆으로 이동하여 다시 탐색하는 방식이다. 0 -> 1 -> 3 -> 4 -> 2 -> 5 -> 6 의 형태로 움직이는 것이다. 미로 찾기 등과 같은 문제를 해결할 때 한 방향으로 끝까지 갈 수 있을 때까지 간 후, 더 이상 갈 수 없으면 가장 가까운 갈림길로 돌아와서 해당 갈림길 방향으로 다시 탐색하는 방식으로 볼 수 있다. 모든 경우의 수를 탐색하고자 할 때 DFS를 사용한다. 그러나, 모든 경우의 수를 ..