[baekjoon] 2001

보석 줍기

문제

n(1 ≤ n ≤ 100)개의 섬이 m(1 ≤ m ≤ 1,000)개의 다리로 연결되어 있다. 각각의 다리는 서로 다른 두 섬을 연결하고 있으며, 서로 다른 두 섬은 최대 한 개의 다리로만 직접 연결되어 있다. 각각의 다리들의 튼튼한 정도는 서로 달라서, 각각의 다리마다 견딜 수 있는 무게의 제한이 다를 수 있다.

섬들 중, K(1 ≤ K ≤ 14)개의 서로 다른 섬에 각각 한 개씩 보석이 있다. 당신은 1번 섬에서 빈손으로 출발하여 최대한 많은 보석을 줍고 1번 섬으로 돌아오려 한다. 주의할 것은, 보석을 너무 많이 줍다 보면 다리를 건널 때 다리가 무게를 견디지 못하고 무너질 수 있다는 점이다. 따라서 당신은 다리가 무너지지 않는 한도 내에서 보석을 주워야 한다.

한 번 지난 적이 있는 다리와 섬을 여러 번 지날 수 있으며, 보석이 있는 섬을 지날 때에 그 보석을 줍지 않을 수도 있다고 하자.

입력

첫째 줄에 n, m, K가 주어진다. 다음 K개의 줄에는 보석이 있는 섬의 번호가 주어진다. 다음 m개의 줄에는 각 다리에 대한 정보를 나타내는 세 자연수 a, b, c(1 ≤ c ≤ 100)가 주어진다. 이는 a번 섬과 b번 섬이 다리로 연결되어 있는데, 그 다리가 최대 c개의 보석만을 견딜 수 있다는 의미이다. 예를 들어 c가 2라면, 그 다리를 지날 때 보석을 0, 1, 2개 가지고 있어야 한다는 의미이다. 3개 이상의 보석을 가지고 그 다리를 지나려고 하면 다리가 무너진다.

출력

첫째 줄에 주울 수 있는 보석의 최대 개수를 출력한다.

예제 입력

6 7 5
1
2
3
4
5
1 2 3
3 6 2
6 2 10
2 4 1
5 1 1
4 5 1
1 6 1

예제 출력

4

풀이

이전에 풀었던 "1194번 - 달이 차오른다, 가자."와 비슷하다.

차이점은 섬을 지날때 보석을 줍고 가는경우 그냥 가능경우를 생각하고 가중치를 검사해준다.

 

#include <iostream>
#include <queue>
#include <memory.h>

using namespace std;

vector<pair<int, int>> *island; // to, weight
int *jewelryIslandList;
int islandNumber, bridgeNumber, jewelryNumber;
bool **visit;

bool isJewelryIsland(int island){
    for(int i = 0; i < jewelryNumber; i++){
        if(jewelryIslandList[i] == island)return true;
    }
    return false;
}
int getJewelryIndex(int island){
    for(int i = 0; i < jewelryNumber; i++){
        if(jewelryIslandList[i] == island)return i;
    }
    return -1;
}

int BFS(int start){
    int answer = 0;
    queue<pair<int, pair<int, int>>> q; // 섬 , 보석 수, 보석 종류

    q.push(make_pair(start, make_pair(0, 0)));
    while(!q.empty()){
        int current = q.front().first;
        int getJewelryNumber = q.front().second.first;
        int jewelryKey = q.front().second.second;

        q.pop();

        //탐색 다하고 돌아온 경우
        if(current == start && answer < getJewelryNumber){
            answer = getJewelryNumber;
        }
        
        if(visit[current][jewelryKey])continue;
        visit[current][jewelryKey] = true;

        for(auto next : island[current]){
            int nextIsland = next.first;
            int nextIslandWeight = next.second;
            // 줍지 않고 이동, 방문하지 않고 가진보석이 가중치보다 작음.
            if(!visit[nextIsland][jewelryKey] && nextIslandWeight >= getJewelryNumber){   
                q.push(make_pair(nextIsland, make_pair(getJewelryNumber, jewelryKey)));
            }
            // 다음 섬에 보석이 있어서 줍는 경우
            if(isJewelryIsland(nextIsland)){
                int jewelryIndex = getJewelryIndex(nextIsland);
                int newkey = jewelryKey + (1 << jewelryIndex);
                if((jewelryKey & (1 << jewelryIndex)) || visit[nextIsland][newkey] || (nextIslandWeight < getJewelryNumber+1 && nextIsland != start))continue;
                q.push(make_pair(nextIsland, make_pair(getJewelryNumber+1, newkey)));                
            }
        }
    }
    return answer;
}



int main(){
    cin >> islandNumber >> bridgeNumber >> jewelryNumber;

    island = new vector<pair<int ,int>>[islandNumber+1];
    visit = new bool *[islandNumber + 1];
    
    int visitSize = (1 << jewelryNumber) + 1;
    for(int i = 0; i < islandNumber + 1; i++){
        visit[i] = new bool[visitSize];
        memset(visit[i], false, sizeof(bool)*visitSize);
    }
    jewelryIslandList = new int[jewelryNumber];
    //보석 입력
    for(int i = 0; i < jewelryNumber; i++)cin >> jewelryIslandList[i];
    
    //다리 입력
    for(int i = 0; i < bridgeNumber; i++){
        int i1, i2, w;
        cin >> i1 >> i2 >> w;

        island[i1].push_back(make_pair(i2, w));
        island[i2].push_back(make_pair(i1, w));
    }
    
    cout << BFS(1);

}