[Algorithm/C++17] 백준 2001 보석줍기

문제

https://www.acmicpc.net/problem/2001

2001번: 보석 줍기

풀이 방법

1194번 달이 차오른다, 가자와 비슷한 문제이다. 이 문제에서는 열쇠를 갖고 이동하는 것이 아니라 보석을 줍고 이동하며, 시작점으로 돌아왔을때 보석의 최대 개수를 출력해야한다.

1194번과 유사하게 보석이 최대 14개이므로 보유한 보석을 최대16,384 (1<<14)로 표현해 비트마스킹으로 해당 보석을 갖고 있는지 확인한다. 거기에 더해 이 문제에서는 보유한 보석의 개수를 구해야하는데, 켜진 비트의 수를 계산해도 되지만 그냥 큐에 넣을때 보석 개수까지 같이 넣어줬다.

 

처음에는 (시작점,아무 보석이 없는 상태, 0개)를 큐에 넣는다.

현재 섬에 보석이 있을 경우 (현재 섬, 해당 보석을 주운 상태, 현재 보석 개수 + 1)를 큐에 넣는다.

그리고 인접한 섬에 대해 건너갈 수 있으면 (인접한 섬, 현재 보석 상태, 현재 보석 개수)를 큐에 넣는다.

이렇게 하면 보석이 있는 섬을 지날 때 보석을 줍지 않는 경우와 줍는 경우 모두 큐에 들어가게 된다.

코드

#include <cstdio>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;
int main()
{
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);
    vector<vector<pair<int,int>>> v(n+1, vector<pair<int,int>>()); // 인접 리스트
    vector<int> jewels(n+1, -1); // 섬이 갖고 있는 보석
    for(int i=0; i<k; i++)
    {
        int t;
        scanf("%d", &t);
        jewels[t] = i; // [t]섬은 i번째 보석을 갖고 있음
    }
    for(int i=0; i<m; i++)
    {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        v[a].push_back({b,c});
        v[b].push_back({a,c});
    }
    queue<tuple<int, int, int>> q; // (섬 번호, 보유 보석, 보석 개수)
    bool visited[101][1<<14] = {false,}; 
    int answer = 0;
    q.push({1, 0, 0});
    visited[1][0] = true;
    while(!q.empty())
    {
        auto p = q.front();
        q.pop();
        int cur = get<0>(p);
        int jewel = get<1>(p);
        int jewel_count = get<2>(p);
        // 시작 섬일 경우 최대 개수를 갱신
        if(cur == 1) answer = max(answer, jewel_count); 
        // 현재 섬의 보석을 갖고있지 않은 경우
        if(jewels[cur] != -1 && !(jewel & 1<<jewels[cur]))
        {
            // 보석을 줍고 탐색하는 경우를 노드에 추가
            int new_jewel = jewel | 1<<jewels[cur];
            visited[cur][new_jewel] = true;
            q.push({cur, new_jewel, jewel_count+1});
        }
        // 인접 섬을 탐색
        for(auto &e : v[cur])
        {
            int next = e.first;
            int bridge = e.second;
            if(visited[next][jewel]) continue;
            if(bridge >= jewel_count)
            {
                visited[next][jewel] = true;
                q.push({next, jewel, jewel_count});
            }
        }
    }
    printf("%d", answer);
    return 0;
}

고찰

채점 중 10%에서 런타임 에러가 발생했었다. 원인을 곰곰이 생각해보니 jewels를 vector<bool>로 선언하고 보석을 갖고있는지 여부를 확인 할 때 잘못하고 있었다.

예를 들면 n번 섬이 k번 보석을 갖고 있다고 하면, jewel & 1<<k를 해줘야 하는데 jewel & 1<<n을 하고 있었다. 이렇게 하면 99번 섬이 보석을 갖고있을때 1<<99번 비트를 확인하므로 OutOfBounds가 발생한다.

 

그래서 jewels를 vector<int>로 바꾸고 보석이 없는 섬이면 -1, 있는 섬이면 0 ~ k-1의 번호를 갖게 했다.

이렇게 하면 n번 섬이 k번 보석을 갖고 있으면 jewels[n] = k가 될 것이다.

그리고 그 보석을 현재 상태가 갖고 있는지 확인하려면 1<<jewels[n] 비트가 켜져있는지 확인하면 된다.