[프로그래머스] 389480 : 완전범죄 [JAVA] Lv.2

프로그래머스

 

문제 풀이 설명 (summary)

• 각 도둑 A,B 가 각각 흔적 누적 개수 이상이 되면 실패한다. 
• A 도둑이 남긴 흔적의 누적개수의 최솟값을 리턴해야 하므로 깊이 우선 탐색을 활용하여 도달했을 때 A도둑의 누적 개수를 기록 하여, 기존값과 비교해서 작은값을 저장해서 관리
• 초기값 그대로라면 -1 출력

 

문제 풀이 접근법

• DFS 방식 가능
• DP 방식 가능

 

풀이 코드 (Code)

import java.util.ArrayDeque;

public class Main {

    public static void main(String[] args) {
        int[][] info = new int[][]{{1,2},{2,3},{2,1}};
        int n = 4;
        int m = 4;

        System.out.println(solution(info, n, m));
    }

    static public int solution(int[][] info, int n, int m) {
        int minA = Integer.MAX_VALUE;
        boolean[][][] visited = new boolean[info.length + 1][n + 1][m + 1];
        ArrayDeque<int[]> stack = new ArrayDeque<>();
        stack.addLast(new int[]{0, 0, 0}); // ← 여기 수정됨

        while (!stack.isEmpty()) {
            int[] pick = stack.pollLast();
            int idx = pick[0];
            int A = pick[1];
            int B = pick[2];

            if (A >= n || B >= m) continue;
            if (visited[idx][A][B]) continue;
            visited[idx][A][B] = true;

            if (idx == info.length) {
                minA = Math.min(minA, A);
                continue;
            }

            int nextA = A + info[idx][0];
            int nextB = B + info[idx][1];

            // A 도둑이 훔치는 경우
            if (nextA <= n && nextA < minA) {
                stack.addLast(new int[]{idx + 1, nextA, B});
            }

            // B 도둑이 훔치는 경우
            if (nextB < m) {
                stack.addLast(new int[]{idx + 1, A, nextB});
            }
        }
        return (minA == Integer.MAX_VALUE) ? -1 : minA;
    }
}

 

 

문제 링크 (Link)

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