[Programmers] 완전범죄 JAVA

반응형

728x90

[Programmers] 완전범죄 - LV 2

---

접근

• dfs (백트래킹)

---

풀이

A와 B도둑이 팀을 이루어 모든 물건을 훔칠 때 A 도둑이 남기는 흔적의 최소 개수를 구하는 문제이다. 2025 코드챌린지 2차 예선 문제로 2 레벨의 문제였는데 많이 어렵게 느껴졌던 2 레벨이었다. dfs를 쓰면 될 거 같은 문제였는데 방문체크가 생각처럼 잘 되지 않아 시간초과가 계속 발생했다. 

 

물건을 A도둑이 훔칠지 B도둑이 훔칠지에 따라 분기가 나눠지는데 배열을 통해 방문체크를 하니 뭔가 잘 맞아떨어지지 않았다.

    private static int minATrail = Integer.MAX_VALUE;

    public static int solution(int[][] info, int n, int m) {
        Set<String> isVisited = new HashSet<>();

        dfs(info, 0, 0, 0, n, m, isVisited);

        return minATrail == Integer.MAX_VALUE ? -1 : minATrail;
    }

그래서 방문체크를 Set으로 수행해 줬다. A도둑의 값과 B도둑의 값 그리고 진행 인덱스를 키로 만들어 어떤 분기에서 만나도 이전에 방문한 경우는 건너뛰도록 처리했다. 

    private static void dfs(int[][] info, int aTrail, int bTrail, int idx, int n, int m, Set<String> isVisited) {
        if (idx == info.length) {
            if (aTrail < n && bTrail < m) {
                minATrail = Math.min(minATrail, aTrail);
            }
            return;
        }

        String key = aTrail + "," + bTrail + "," + idx;
        if (isVisited.contains(key)) {
            return;
        }

        if (aTrail + info[idx][0] < n) {
            dfs(info, aTrail + info[idx][0], bTrail, idx + 1, n, m, isVisited);
        }

        if (bTrail + info[idx][1] < m) {
            dfs(info, aTrail, bTrail + info[idx][1], idx + 1, n, m, isVisited);
        }

        isVisited.add(key);
    }

배열의 끝에 도달하게 되면 각 도둑이 경찰에 붙잡히지 않는 흔적의 개수를 만족하는지 체크하고 만족한다면 A도둑의 흔적 개수를 더 작은 값으로 최신화한다. 배열 끝이 아니라면 현재 상황이 방문했던 상황인지를 Set을 통해 검사한다. 방문하지 않았다면 각 도둑들이 현재 물건을 훔칠 수 있다면 훔친 뒤 현재 상황을 Set에 넣는다. 

---

전체 코드

import java.util.*;

class Solution {
    private static int minATrail = Integer.MAX_VALUE;

    public static int solution(int[][] info, int n, int m) {
        Set<String> isVisited = new HashSet<>();

        dfs(info, 0, 0, 0, n, m, isVisited);

        return minATrail == Integer.MAX_VALUE ? -1 : minATrail;
    }

    private static void dfs(int[][] info, int aTrail, int bTrail, int idx, int n, int m, Set<String> isVisited) {
        if (idx == info.length) {
            if (aTrail < n && bTrail < m) {
                minATrail = Math.min(minATrail, aTrail);
            }
            return;
        }

        String key = aTrail + "," + bTrail + "," + idx;
        if (isVisited.contains(key)) {
            return;
        }

        if (aTrail + info[idx][0] < n) {
            dfs(info, aTrail + info[idx][0], bTrail, idx + 1, n, m, isVisited);
        }

        if (bTrail + info[idx][1] < m) {
            dfs(info, aTrail, bTrail + info[idx][1], idx + 1, n, m, isVisited);
        }

        isVisited.add(key);
    }
}