본문으로 건너뛰기

1298 - Maximum Candies You Can Get from Boxes

info

풀이 키워드​

스포주의

bfs 구현


풀이 코드​

info
  • 메모리: 57020 KB
  • 시간: 3 ms
class Solution {
    public int maxCandies(int[] status, int[] candies, int[][] keys, int[][] containedBoxes, int[] initialBoxes) {
        boolean[] visited = new boolean[status.length];
        boolean[] haveKey = new boolean[status.length];

        // init
        Deque<Integer> q = new ArrayDeque<>();
        for (int i : initialBoxes) {
            q.add(i);
            visited[i] = true;
            for (int j : keys[i]) haveKey[j] = true;
        }
        
        // break condition: found no key & box == hopeless
        boolean hope = true;
        int ans = 0;
        while (hope) {
            int sz = q.size();
            hope = false;
            while (sz-- > 0) {
                int i = q.poll();
                if (status[i] == 1 || (status[i] == 0 && haveKey[i])) { // 1. opened or can open
                    for (int k : keys[i]) {
                        if (haveKey[k]) continue; // useless key
                        haveKey[k] = true; // get keys
                        hope = true;
                    }
                    for (int b : containedBoxes[i]) {
                        if (visited[b]) continue;
                        q.add(b); // get boxes
                        visited[b] = true;
                        hope = true;
                    }
                    ans += candies[i];
                }
                else { // 2. closed or can't open
                    q.add(i);
                }
            }
        }

        return ans;
    }
}

풀이 해설​

지문의 내용에 따라 그대로 조건을 구현해서 bfs로 풀이하는 문제이다.


📦 보유 중인 박스는 큐로 저장하기​

Deque<Integer> q = new ArrayDeque<>();
for (int i : initialBoxes) {
    q.add(i);
    visited[i] = true;
    for (int j : keys[i]) haveKey[j] = true;
}

initialBoxes에 주어진 시작 박스들을 전부 큐에 넣고, 중복 삽입하지 않도록 방문 처리한다.

그리고 보유중인 박스에 대한 모든 key들도 보유 처리한다.

haveKey는 그냥 쉽게 생각해서 key에 대한 boolean 타입 visited이다.

이걸로 keys[i]에 대한 방문 판별도 하고 보유 판별도 한다.

key도 방문 처리하는 이유는 이미 예전에 2번 키 사용했었는데 다른 상자에서 또 2번 키 나왔다고 희망이 생기면 안되기 때문이다.


"언제까지 희망고문 할건데"​

// break condition: found no key & box == hopeless
boolean hope = true;
int ans = 0;
while (hope) {
    int sz = q.size();
    hope = false;
    while (sz-- > 0) {
        ...
    }

문제 풀이에 가장 시간을 투자한 부분인데, bfs를 돌리다가 어느 기준으로 while을 빠져나올지 고민되었다.

왜냐하면 큐의 박스들을 다 스캔해서 key나 containedBox를 찾아보아도 아무 진척이 없을 때

이는 더이상의 탐색이 의미없어 while문을 종료할 타이밍이지만,
여전히 큐에는 박스들이 남아있기 때문이다. (즉, !q.isEmpty() 사용 불가)

따라서 큐의 박스들을 한차례 다 스캔하는 것을 1 wave로 기준잡아 wave당 큐 size만큼 순회했고

size만큼 순회하는동안 쓸만한 key나 containedBox를 찾았다면 hope를 true로 설정해서 bfs라는 희망고문을 계속하도록 로직을 구성했다.


메모​

  • while문 구성만 약간의 생각이 필요한 부분이고 다른건 무난한 난이도이다.
  • NextLeet의 존재를 알게되었다. 여행 가기 전 미리 풀어두면 좋을듯?