프로그래머스 Level 2 피로도

피로도

출처: 프로그래머스

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

프로그래머스

이 포스트는 광고 게시가 없는 비상업적 비영리적 포스트임을 알려드립니다.

 

문제

제한 사항

설명

저는 dfs로 각 던전을 하나씩 탐험하며 던전 탐험이 끝났을 때 최대를 비교하면 풀 수 있지 않을까 생각했습니다.제한 사항에 dungeons의 개수가 1개부터 8개까지 있으므로 시간 복잡도를 고려하지 않아도 dfs로 충분히 가능하겠구나 생각했습니다.

 

이제 제가 어떻게 풀었는지 한번 얘기해 보겠습니다.

 

저는 dfs를 생각 후에 먼저 제한사항을 확인했습니다. 1-8개 이므로 충분하다 생각하였고 모든 경우를 돌면서 현재 가지고 있는 피로도로 입장할 수 있다면 입장하면 되겠다고 생각했습니다.

 

과정을 볼까요? 

 

아래에 예시가 있습니다.

먼저 현재 피로도 80으로 갈 수 있는 맨 앞에부터 확인해 봅니다.

 

index가 0일 때

입장 컷 피로도 = 80 

소모 피로도 = 20

0번 던전에 들어갑니다.

 

던전에 들어갔다 오면 피로도 k = 80 - 20이 됩니다. 

이제 60의 피로도를 가지고 다음 던전을 탐색합니다.

 

돌아가는 곳

0번 index는 방문했으므로 패스하고

1번을 보면 1번은 방문하지 않았고 입장도 가능합니다.

던전에 들어갔다 나옵니다.

 

 

 

피로도 = 60-40 = 20이 남고 20을 가지고 다시 던전을 찾으러 갑니다

 

0번과 1번은 방문했으니 3번을 보는데 3번은 최소 30 피로도는 있어야 입장이 가능합니다.

더 이상 갈 수 있는 곳이 없습니다.

 

 

 

이제 현재까지의 maxCnt 최대 값과 cnt를 비교합니다.

maxCnt는 아직 갱신된 적이 없어 0이고 cnt는 현재 2개의 던전을 돌아 2입니다. 

더 큰 값이 2이므로 2를 반환하고 다시 돌아가는데 어디로 가냐   

 

여기로 다시 돌아갑니다.

여기가 어디냐 0번 던전을 돌고 1번을 돌았을 때입니다.

여기서 이제 1번 던전을 방문했던 기록을 지우고 2번으로 갑니다 

 

현재 0번을 돌고 2번을 도는 경우로 넘어가게 됩니다.

이런 방식이 순열입니다. 

순열은 나열할 수 있는 모든 경우의 수입니다.

 

이렇게 dfs를 이용해 갈 수 있는 방법의 던전 경로를 모두 파악합니다.

던전 갈 수 있는 끝까지 가보고 최댓값 비교하고 다시 하나 돌아가 다음 던전 갈 경우 따지고...

 

이해가 좀 되시나요?? 어쩌다 보니 dfs를 이용한 순열의 작동 방식을 설명하고 있네요.

 

아래에 코드가 있습니다.

fun dfs(
    dungeons: Array<IntArray>,
    visited: BooleanArray,
    tired: Int,
    maxCnt: Int,
    cnt: Int
) : Int {
    var m = maxCnt
    for(i in dungeons.indices) {
        if(!visited[i] && tired >= dungeons[i][0]){
            
        }
    }
    return max(m, cnt)
}

 

가운데 if문을 보면 방문하지 않았고 현재 피로도 tired로 방문이 가능하다면 dungeons에 들어갈 수 있으므로 if문 안으로 진입합니다.

 

 

안으로 진입 후에 방문처리를 하고 다음 던전을 탐색하기 위해 dfs로 들어갑니다.

만약 새로운 dfs에서 더 이상 방문하지 않았고 가지고 있는 피로도로 들어갈 수 있는 던전이 없다면 지금까지 던전을 돌았던 경로 중 가장 큰 값을 저장해 둔 m과 현재 과정으로 입장한 던전의 수인 cnt를 비교하여 더 큰 값을 반환합니다.

 

if(!visited[i] && tired >= dungeons[i][0]){
    visited[i] = true
    m = dfs(dungeons, visited, tired-dungeons[i][1], m, cnt+1)
    visited[i] = false
}

 

전체 코드를 보겠습니다.

 

import kotlin.math.max

class Solution {
    fun solution(k: Int, dungeons: Array<IntArray>): Int = dfs(dungeons, BooleanArray(dungeons.size){false}, k, 0, 0)

    fun dfs(
        dungeons: Array<IntArray>,
        visited: BooleanArray,
        tired: Int,
        maxCnt: Int,
        cnt: Int
    ) : Int {
    	//가장 큰 값을 변경해서 반환하기 위한 m
        var m = maxCnt
        // 던전을 탐색합니다.
        for(i in dungeons.indices) {
        	// 방문하지 않은 던전이면서 입장이 가능한지 확인합니다.
            if(!visited[i] && tired >= dungeons[i][0]){
            	// 방문처리하고
                visited[i] = true
                // dungeonCnt를 들어가 다시 탐색합니다.
                m = dfs(dungeons, visited, tired-dungeons[i][1], m, cnt+1)
                // i번을 들어갔다가 나온 경우 i+1을 들렸다가 갈 경우를 위해 false로 돌립니다.
                visited[i] = false
            }
        }
        // 둘 중에 큰 값을 반환합니다.
        return max(m, cnt)
    }
}

 

if문 안으로 가 다시 dfs를 실행합니다.

 

 

결과는 아래와 같습니다.

 

 

도움이 되길 바라면서 이만 마치겠습니다. 궁금하신 점이 있으시면 댓글 부탁드립니다~