[프로그래머스 | 파이썬 / 자바스크립트] 피로도(완전탐색/ level 2)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/87946

프로그래머스

 

 

🐍파이썬

from itertools import permutations 
def solution(k, dungeons):
    result = []
    #던전을 방문하는 순서의 경우의 수를 나열
    for dg in permutations(dungeons, len(dungeons)):	
        nk = k	#매번 k로 피로도 리셋
        answer = 0	#방문한 던전 수 매번 리셋
        for d in dg:	#각 경우의 수마다 방문할 수 있는 던전 수 확인
            if nk >= d[0]:	#남은 피로도가 던전의 필요피로도보다 같거나 큰 경우 던전 방문
                nk -= d[1]	#남은 피로도-소모 피로도
                answer += 1 	#방문한 던전 수 + 1
        result.append(answer)
    return max(result)	#방문 가능한 최대 던전의 수

❓ 순열

itertools.permutations(iterable, r=None)

• itertools 모듈
• 서로 다른 n개 원소 중 r개를 순서를 고려해 나열하는 경우의 수
• 위 코드의 경우 순열은 아래와 같다.

...
def solution(k, dungeons):
    result = []
    for dg in permutations(dungeons, len(dungeons)):
        print(dg)
        # dungeons = [[80,20],[50,40],[30,10]]일때
        # 순열의 결과
        # ([80, 20], [50, 40], [30, 10])
        # ([80, 20], [30, 10], [50, 40])
        # ([50, 40], [80, 20], [30, 10])
        # ([50, 40], [30, 10], [80, 20])
        # ([30, 10], [80, 20], [50, 40])
        # ([30, 10], [50, 40], [80, 20])
        nk = k
       ...

 

 

다른 풀이 방법

answer = 0
N = 0
visited = []
 
def dfs(k, cnt, dungeons):
    global answer
    if cnt > answer:	#방문가능한 던전의 갯수(cnt)가 answer보다 더 크다면 리턴할 최대 던전의 갯수를 cnt개로 설정 
        answer = cnt
    for j in range(N):
        if k >= dungeons[j][0] and not visited[j]:	#현재 피로도로 방문할 수 있는 던전이면서 방문하지 않은 던전인 경우
            visited[j] = 1	#방문처리
            dfs(k - dungeons[j][1], cnt + 1, dungeons)	#dfs(현재피로도 업데이트, 방문횟수 체크, 던전배열)
            visited[j] = 0	#dfs의 리프노드까지 모두 탐색 후 이전 노드로 돌아왔을 경우, 해당 노드 visited값을 0으로 복구
 
def solution(k, dungeons):
    global N, visited
    N = len(dungeons)
    visited = [0] * N
    dfs(k, 0, dungeons)	#방문한 던전갯수 0개
    return answer

DFS를 이용한 풀이

 

 

🐥자바스크립트

let answer = 0
let cnt = 0
let visited;
 
function DFS(k, cnt, dungeons){
    // 방문가능한 던전의 갯수(cnt)가 answer보다 더 크다면 리턴할 최대 던전의 갯수를 cnt개로 설정 
    if(cnt > answer){
        answer = cnt;
    }
    for(let i = 0; i < dungeons.length; i++){
        // 현재 피로도로 방문할 수 있는 던전이면서 방문하지 않은 던전인 경우
        if(k >= dungeons[i][0] && visited[i] == 0){
            visited[i] = 1;	// 방문처리
            DFS(k - dungeons[i][1], cnt+1, dungeons);	// DFS(현재피로도 업데이트, 방문횟수 체크, 던전배열)
            visited[i] = 0;	// DFS의 리프노드까지 모두 탐색 후 이전 노드로 돌아왔을 경우, 해당 노드 visited값을 0으로 복구
        }
    }
}
 
function solution(k, dungeons) {
    (visited = []).length = dungeons.length;	
    visited.fill(0);	//배열 선언. new Array(N).fill(0)보다 속도가 빠르다고 함
    DFS(k, 0, dungeons);	//방문한 던전갯수 0개
    return answer;
}

위 파이썬 DFS와 동일한 로직으로 풀었다.

 

 

참고

자바스크립트 블록 스코프

https://poiemaweb.com/es6-block-scope

let, const | PoiemaWeb

 

자바스크립트 배열 선언

https://miiingo.tistory.com/272

[Node.js] Javascript: 지정한 길이에 맞게 배열을 선언하고 값을 초기화하는 방법들

 

DFS

https://han-py.tistory.com/242

[코딩테스트] 쉽게 이해하고 바로 쓰는 DFS (깊이 우선 탐색)