완전탐색

프로그래머스 레벨2 피로도 문제이다.

이 문제를 풀면서 dfs의 동작 방식에 대해 좀 더 잘 이해할 수 있었던것 같다.

 

풀이

  1. 각 던전의 인덱스에 해당하는 방문 기록 visited를 만든다.
  2. for 문을 돌려서 인덱스에 해당하는 던전에 방문하지 않았고, 입장 시 필요한 피로도를 충족한 경우를 찾는다.
  3. 방문 기록을 남기고 다음 depth로 깊이 우선 탐색을 실행한다.
  4. for 문의 다음 루프에 영향이 가지 않도록 visited 를 초기화 한다.
  5. 재귀함수를 돌아서 가장 깊은 depth 까지 탐색을 한 경우의 depth를 기록한다.

최종 코드

import java.util.*;
class Solution {
    static int answer = 0;
    static boolean[] visited;
    
    public void dfs(int[][] dungeons, int left, int depth) {
    	// 2. for 문을 돌려서 인덱스에 해당하는 던전에 방문하지 않았고, 
        // 입장 시 필요한 피로도를 충족한 경우를 찾는다.
        for (int i = 0; i < dungeons.length; i++) {
            if (visited[i] == false && left >= dungeons[i][0]) {
            	// 3. 방문 기록을 남기고 다음 depth로 깊이 우선 탐색을 실행한다.
                visited[i] = true;
                dfs(dungeons, left - dungeons[i][1], depth +1);
                // 4. for 문의 다음 루프에 영향이 가지 않도록 visited 를 초기화 한다.
                visited[i] = false;
            }
        }
        // 5. 재귀함수를 돌아서 가장 깊은 depth 까지 탐색을 한 경우의 depth를 기록한다.
        answer = Math.max(answer, depth);
    }
    public int solution(int k, int[][] dungeons) {
    	// 1. 각 던전의 인덱스에 해당하는 방문 기록 visited를 만든다.
        visited = new boolean[dungeons.length];
        int left = k;
        dfs(dungeons, left, 0);
        return answer;
    }
}

'알고리즘 > 완전탐색' 카테고리의 다른 글

[알고리즘] 소수찾기  (0) 2023.11.12

완전탐색

프로그래머스 레벨2 소수 찾기 문제이다.

완전탐색은 dfs 와 비슷한 방식인듯 싶기도 한데, 익숙해지려면 좀 더 많은 문제를 풀어봐야 겠다.

 

풀이

  1. 재귀 함수를 통해 완전 탐색하여 만들 수 있는 모든 숫자를 int 로 변환한다.
  2. 각 숫자를 소수 판별하여 소수일 경우 set 에 추가한다. (각 숫자의 제곱근까지만 약수의 여부 검증)
  3. set 의 사이즈가 이 문제의 답

최종 코드

import java.util.*;
class Solution {
    Set<Integer> set = new HashSet<>();
    
    // 소수 판별 메서드
    public boolean isPrime(int item) {
        if (item <= 1) {
            return false;
        }
        int limit = (int) Math.sqrt(item);
        for (int i = 2; i <= limit; i++) {
            if (item % i == 0) {
                return false;
            }
        }
        return true;
    }
    
    // 재귀 함수
    public void reculsive(String start, String rest) {
        if (!start.equals("")) {
            int item = Integer.parseInt(start);
            // 소수 판별
            if (isPrime(item)) {
                set.add(item);
            }
        }
        for (int i = 0; i < rest.length(); i++) {
            reculsive(start + rest.charAt(i), 
                rest.substring(0, i) + rest.substring(i+1));
        }
    }
    
    public int solution(String numbers) {
        reculsive("", numbers);
        return set.size();
    }
}

'알고리즘 > 완전탐색' 카테고리의 다른 글

[알고리즘] 피로도  (0) 2023.11.16

+ Recent posts

티스토리툴바