Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++ BFS 탐색으로 상자에서 얻을 수 있는 최대 사탕 개수 구하기

문제 개요

n개의 상자가 주어지며, 각 상자는 [status, candies, keys, containedBoxes] 형식으로 표현됩니다. 이때 다음과 같은 제약 조건이 존재합니다.

  • status[i]: box[i]가 열려 있으면 1, 닫혀 있으면 0입니다.
  • candies[i]: box[i]에 들어 있는 사탕의 개수입니다.
  • keys[i]: box[i] 안의 열쇠로 열 수 있는 상자 인덱스들의 배열입니다.
  • containedBoxes[i]: box[i] 안에서 발견되는 상자 인덱스들의 배열입니다.

initialBoxes 배열에 담긴 상자부터 시작해, 열려 있는 상자의 사탕은 모두 가져갈 수 있고, 상자 안의 열쇠로 새로운 상자를 열거나 발견한 상자를 꺼내 사용할 수 있습니다. 위 규칙에 따라 얻을 수 있는 최대 사탕 개수를 구하는 것이 이 문제의 목표입니다.

예제로 이해하기

입력이 다음과 같다고 가정해 보겠습니다.

status = [1,0,1,0]
candies = [8,6,5,101]
keys = [[], [], [1], []]
containedBoxes = [[1,2],[3],[],[]]
initialBoxes = [0]

이 경우 출력은 19입니다. 과정을 하나씩 살펴보면 다음과 같습니다.

  1. 처음에 상자 0이 주어지며, 그 안에서 사탕 8개와 상자 1, 2를 발견합니다.
  2. 상자 1은 닫혀 있고 열쇠도 없으므로 열 수 없습니다. 대신 상자 2를 엽니다.
  3. 상자 2에서 사탕 5개와 상자 1의 열쇠를 얻습니다.
  4. 얻은 열쇠로 상자 1을 열어 사탕 6개와 상자 3을 발견합니다. 하지만 상자 3의 열쇠는 없으므로 상자 3은 끝내 열지 못합니다.
  5. 따라서 총 수집한 사탕은 8 + 5 + 6 = 19개입니다.

풀이 접근 방법: BFS(너비 우선 탐색)

이 문제는 큐(queue)를 이용한 BFS로 자연스럽게 해결할 수 있습니다. 핵심은 다음 세 가지 상태를 집합(set)으로 관리하는 것입니다.

  • visited: 현재 손에 쥔(확인한) 상자
  • opened: 이미 열어서 사탕을 수집한 상자
  • hasKey: 열쇠를 확보한 상자

상자를 실제로 열기 위해서는 '상자를 가지고 있으면서(visited)', '처음부터 열려 있거나(status=1) 열쇠가 있어야(hasKey)' 한다는 점이 핵심입니다. 두 조건이 동시에 충족되는 순간 큐에 넣고 처리하면, 열쇠와 상자가 서로 다른 순서로 발견되더라도 누락 없이 모든 상자를 처리할 수 있습니다.

알고리즘 단계

  1. 정답 변수 ans := 0으로 초기화합니다.
  2. 큐 q와 집합 visited, opened, hasKey를 준비합니다.
  3. initialBoxes의 각 상자 x에 대해 방문 처리(visited에 추가)하고, 이미 열려 있는 상자(st[x] == 1)라면 사탕을 더하고(ans += cnt[x]) opened와 q에 넣습니다.
  4. 큐가 빌 때까지 반복합니다.
    • 큐에서 상자 curr를 꺼냅니다.
    • curr가 가진 각 열쇠 x에 대해 hasKey에 추가하고, x를 아직 열지 않았지만 손에 들고 있다면(visited에 존재) 즉시 열어 사탕을 수집한 뒤 q에 넣습니다.
    • curr 안에서 발견한 각 상자 x에 대해 visited에 추가하고, 아직 열지 않았으며 (열쇠가 있거나 처음부터 열려 있다면) 바로 열어 사탕을 수집한 뒤 q에 넣습니다.
  5. 모든 탐색이 끝나면 ans를 반환합니다.

C++ 구현 코드

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int maxCandies(vector<int>& st, vector<int>& cnt,
   vector<vector<int>>& k, vector<vector<int>>& cb, vector<int>& ib) {
      int ans = 0;
      queue<int> q;
      set<int> visited;
      set<int> opened;
      set<int> hasKey;
      for (int i = 0; i < ib.size(); i++) {
         int x = ib[i];
         visited.insert(x);
         if (st[x] == 1) {
            ans += cnt[x];
            opened.insert(x);
            q.push(x);
         }
      }
      while (!q.empty()) {
         int curr = q.front();
         q.pop();
         for (int i = 0; i < k[curr].size(); i++) {
            int x = k[curr][i];
            hasKey.insert(x);
            if (!opened.count(x) && visited.count(x)) {
               ans += cnt[x];
               q.push(x);
               opened.insert(x);
            }
         }
         for (int i = 0; i < cb[curr].size(); i++) {
            int x = cb[curr][i];
            visited.insert(x);
            if (!opened.count(x) && (hasKey.count(x) || st[x] ==
            1)) {
               opened.insert(x);
               ans += cnt[x];
               q.push(x);
            }
         }
      }
      return ans;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,0,1,0}, v1 = {8,6,5,101}, v2 = {0};
   vector<vector<int>> v3 = {{},{},{1},{}}, v4 = {{1,2},{3},{0},{}};
   cout << (ob.maxCandies(v, v1, v3, v4, v2));
}

실행 결과 확인

입력:

{1,0,1,0}, {8,6,5,101}, {{},{},{1},{}}, {{1,2},{3},{0},{}}, {0}

출력:

19

복잡도 및 마무리

각 상자는 최대 한 번만 큐에서 처리되고, 모든 열쇠·포함 관계도 한 번씩만 검사하므로 전체 시간 복잡도는 상자 수와 내부 요소 수에 비례하는 O(N) 수준이며, 공간 복잡도 역시 상태 집합과 큐를 위해 O(N)입니다. 성능이 중요하다면 std::set 대신 std::unordered_set을 사용하면 조회 비용을 더 줄일 수 있습니다.

이 문제의 핵심은 단순한 그래프 탐색이 아니라, '상자를 소유하고 있는가'와 '열 수 있는가'라는 두 조건이 동시에 만족되는 시점을 정확히 포착하는 것입니다. BFS와 상태 집합을 함께 활용하면 열쇠와 상자가 어떤 순서로 발견되더라도 놓치는 사탕 없이 최댓값을 구할 수 있습니다.