[프로그래머스/파이썬] 피로도 풀이
(dfs, 백트래킹, 완전탐색)
1. 문제
https://school.programmers.co.kr/learn/courses/30/lessons/87946
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
2. 사전 개념
2.1. 백트래킹(Backtracking)
- 가능한 모든 경우의 수를 탐색하면서 조건을 만족하는 경우만을 채택하는 방법이다.
- 조건을 만족하지 않으면 그 경로를 더 이상 탐색하지 않고 되돌아간다.
- 이 과정에서 '가지치기'를 수행하여 비효율 적인 탐색을 방지하는 것.
- 참고 :https://chanhuiseok.github.io/posts/algo-23/
2.2. DFS (Depth-Frist Search)
- 깊이 우선 탐색이라는 뜻으로, 그래프나 트리를 한 경로로 최대한 깊숙이 들어가서 노드를 탐색하는 방법이다.
- 한 방양으로 갈 수 있을 때까지 계속 가다가, 더 이상 진행할 수 없으면 되돌아와서 다른 경로를 탐색한다.
- stack 자료구조를 사용한다. (재귀로도 가능)
- 참고 : https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html
2.3. 백트래킹과 DFS
- dfs는 가능한 경로를 끝까지 탐색한다.
- 백트래킹을 포함한 dfs에서는 탐색 도중, 특정 조건을 만족하지 않는 경우 '가지치기'를 수행하여 불필요한 경로를 더 이상 탐색하지 않는다.
- 또한, 백트래킹을 적용하여 탐색을 되돌아갈 경우, 방문 여부나 개수 등을 그 당시 노드가 가지고 있던 것으로 복구해야 한다.
2. 코드
# 결과, 방문 개수(깊이), 내 피로도, 방문 표시 배열, 던전 배열
def DFS(answer, count, k, visited, dungeons):
answer = max(answer, count)
for i in range(len(dungeons)): # 던전 개수만큼 각각 방문
if k < dungeons[i][0] or visited[i]: #최소 필요 피로도가 더 크거나, 이미 방문한 던전이면
continue
#아니라면 현재 던전을 방문한다.
visited[i] = True #방문 처리
# 그리고 다음 던전도 방문한다.
# 던전 방문수 +1, 내 피로도 - 현재 던전 소모 필요도, 방문처리된배열,던전배열
answer = DFS(answer, count+1, k-dungeons[i][1], visited, dungeons)
# 그리고 다시 방문 처리를 돌려놓는다.
# 두번째는 또 다르게 방문할것이기 때문에
visited[i] = False
return answer
def solution(k, dungeons):
answer = 0
# 방문 처리 배열
visited = [False] * len(dungeons) # 던전 개수만큼
count = 0 # dfs 깊이 (방문한 개수)
# k : 피로도
# answer : 결과
answer = DFS(answer, count, k, visited, dungeons)
return answer3. 풀이
1. 풀이 방식은 다음과 같다.
- 주어진 피로도와 탐험한 던전 개수를 가지고 던전개수만큼 던전번호를 매겨서(0,1,2) 계속 dfs 하면 된다.
- 그러면 던전 가는 순서가 0 -> x , 백트래킹, 0->1->x, 백트래킹, 0->2->1 이런 식으로.. DFS가 계속해서 진행되는 것이다.
- DFS를 진행하면서 answer에 계속 count랑 비교해서 제일 큰 값을 반환하면 제일 많이 간 던전 횟수(깊이)가 저장된다!
- 중요한 건, 백트래킹하면 다시 이전 번호로 돌아가는 것이기 때문에, visited를 다시 되돌려 줘야 한다! 0->1번을 갔다가 다시없어서 0번으로 되돌아올 때, 1번은 다시 방문 안 한 걸로 False로 바꿔주면 된다. 그래야 0->1->다음 2번으로 갈 수 있기 때문이다.
1. 초기화
def solution(k, dungeons):
answer = 0
# 방문 처리 배열
visited = [False] * len(dungeons) # 던전 개수만큼
count = 0 # dfs 깊이 (방문한 개수)
# k : 피로도
# answer : 결과
answer = DFS(answer, count, k, visited, dungeons)
return answer- 방문 처리 배열 : 던전을 방문했는지 확인할 배열로, 배열을 초기화해 준다.
- count : 던전을 방문한 개수이다. (dfs의 깊이와 같다)
2. DFS 선언
# 결과, 방문 개수(깊이), 내 피로도, 방문 표시 배열, 던전 배열
def DFS(answer, count, k, visited, dungeons):
answer = max(answer, count)
for i in range(len(dungeons)): # 던전 개수만큼 각각 방문
if k < dungeons[i][0] or visited[i]: #최소 필요 피로도가 더 크거나, 이미 방문한 던전이면
continue
#아니라면 현재 던전을 방문한다.
visited[i] = True #방문 처리
# 그리고 다음 던전도 방문한다.
# 던전 방문수 +1, 내 피로도 - 현재 던전 소모 필요도, 방문처리된배열,던전배열
answer = DFS(answer, count+1, k-dungeons[i][1], visited, dungeons)
# 그리고 다시 방문 처리를 돌려놓는다.
# 두번째는 또 다르게 방문할것이기 때문에
visited[i] = False
return answer
2.1. answer에는 최대 던전 방문 개수를 저장한다.
answer = max(answer, count)
2.2. 던전 개수만큼 반복하며 dfs를 실행한다.
- 최소 필요 피로도가 더 크거나 이미 방문한 던전이면 지나친다.
if k < dungeons[i][0] or visited[i]: #최소 필요 피로도가 더 크거나, 이미 방문한 던전이면
continue
- 만약 방문 가능한 던전이라면, 던전을 방문한다.
visited[i] = True #방문 처리
# 그리고 다음 던전도 방문한다.
# 던전 방문수 +1, 내 피로도 - 현재 던전 소모 필요도, 방문처리된배열,던전배열
answer = DFS(answer, count+1, k-dungeons[i][1], visited, dungeons)
# 그리고 다시 방문 처리를 돌려놓는다.
# 두번째는 또 다르게 방문할것이기 때문에
visited[i] = False방문처리를 해주고, DFS를 다시 실행한다.
이때, 던전을 한번 방문했으니 현재 방문수 +1 (cont+1)
현재 던전 방문 후 남은 피로도 계산 (k-dungeons [i][1])
을 계산해서 다음 DFS로 넘겨주면 된다!
4. 마무리
Lv2 프로그래머스 문제입니다. 레벨이 낮아서 처음에는 단순 그리디로 풀어야 하나 하면서 풀다가,
너무 문제가 안 풀려서 풀이를 찾아보니, 알고 보니 dfs / 백트래킹 (혹은 순열) 문제였습니다..
알고리즘 너무 어렵다!!
- 직접 공부하면서 정리한 내용이라 틀린 부분이 있을수도 있습니다!
- 틀린 부분이 있으면 말씀해주시면 감사하겠습니다😊
- 풀이 참고
- https://chanhuiseok.github.io/posts/algo-23/
- https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html
'코딩테스트 > 파이썬' 카테고리의 다른 글
| [프로그래머스/파이썬] 네트워크 풀이 ( dfs , 재귀함수, Python ) (0) | 2025.03.01 |
|---|---|
| [프로그래머스/파이썬] 타겟 넘버 풀이 (Python, dfs, 재귀함수) (0) | 2025.02.28 |
| [프로그래머스/파이썬] 더 맵게 풀이 (Python, heap, heapq, heapify, heappush, heappop, 최소힙) (0) | 2025.02.21 |
| [프로그래머스/파이썬] 가장 큰 수 풀이 (Python, sort) (0) | 2025.02.20 |
| [백준/30993/파이썬] 자동차 주차 (4) | 2024.01.21 |
댓글