[프로그래머스 Lv2] 완전 범죄 - Javascript 풀이

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

프로그래머스

---

문제

도둑 A, B가 모든 물건을 훔칠 때 도둑 A의 최소 흔적 개수를 찾는 문제

 

생각

info의 최대 길이가 40이라 DFS로 풀면 시간초과가 날 것이라 생각했다.

그럼에도 DFS 코드로 문제를 풀어보고자 했다. ( DP 같이 다른 풀이 방법이 안 떠오름 .. )

결론 : 제한 조건이 있어 DFS로도 풀린다.

 

문제풀이

큐는 (훔칠 물건의 인덱스, A의 흔적 개수, B의 흔적 개수)를 가진다.

 

하나의 물건당 두가지 경우가 존재한다.

1. A가 물건을 훔치는 경우

2. B가 물건을 훔치는 경우

 

만약, A의 흔적 개수가 n 이상이거나 B의 흔적 개수가 m 이상이면 해당 경우는 더이상 탐색하지 않아도 된다.

모든 물건을 훔쳤을 때 ( index ==  info.length ) 마다 A의 최소 흔적 개수를 업데이트 해주면 된다.

---

생각해볼 점 ↓

문제에서 제한 조건 없이 최소 값을 찾는 것이라면,  2⁴⁰ ≈ 1조 : 완전 탐색해야 하므로 시간 초과가 발생한다.

 

하지만

물건을 훔칠 때 생기는 흔적의 개수 0~3으로 작고,

n, m이 최대 120으로 제한되어 있기 때문에 탐색 상태는 (cur, a, b) 조합으로 제한된다.

그러므로, info.length x n x m = 40 x 120 x 120 = 576,000 

약 57만개의 상태가 나올 수 있고, 시간 초과는 발생하지 않는다.

 

예시를 통해 이해해보자.

info = [[1, 2], [1, 2]], n=10, m=10

단계	설명	(cur, a, b) 상태
시작	아무것도 안 훔침	(0, 0, 0)
1번 물건 훔침	A가 훔침	(1, 1, 0)
	B가 훔침	(1, 0, 2)
2번 물건 훔침	(1, 1, 0)에서 A가 훔침	(2, 2, 0)
	(1, 1, 0)에서 B가 훔침	(2, 1, 2)
	(1, 0, 2)에서 A가 훔침	(2, 1, 2)
	(1, 0, 2)에서 B가 훔침	(2, 0, 4)

 

여기서 상태 (2, 1, 2)가 중복 생성된다.

- 경로 A: (0, 0, 0) → (1, 1, 0) → (2, 1, 2)

- 경로 B: (0, 0, 0) → (1, 0, 2) → (2, 1, 2)

 

이때, 방문 체크가 없다면 (2, 1, 2)를 두번 큐에 넣고

또 거기서 다음 물건을 처리하며 또 똑같은 상태가 계속 무한 중복 될 것이다.

그렇기 때문에 추가로 상태에 대한 방문 체크를 해줘야 한다.

 

 

 

코드

function solution(info, n, m) {
    var answer = 121
    const visited = new Set()
    const queue = [[0, 0, 0]]
    
    while( queue.length !== 0 ) {
        const [cur, a, b] = queue.pop()
        
        // 방문 상태 체크
        const key = `${cur}-${a}-${b}`
        if (visited.has(key)) continue;
        visited.add(key);
        
        if ( a >= n || b >= m ) continue
        if ( cur == info.length ) { // 마지막 물건까지 훔친 경우
            if ( answer > a ) answer = a // 최소 흔적 개수 업데이트
            continue
        }
        
        // 1. A가 물건을 훔치는 경우 = B가 물건을 훔치지 않는 경우 
        queue.push([cur+1, a+info[cur][0], b])
        // 2. B가 물건을 훔치는 경우
        queue.push([cur+1, a, b+info[cur][1]])
    }
    
    return answer === 121 ? -1 : answer
}