[BOJ] 보석 줍기(2001)

[백준(BOJ)] 2001_보석 줍기 JAVA

문제 : BOJ_2001번 보석 줍기

문제 설명

최대 100개의 섬이 있고 각 섬마다 최대 한 가지의 양방향 다리로 연결되어 있습니다.

각 섬마다 보석이 있는 섬과 없는 섬이 있고, 다리마다 보석을 견딜 수 있는 수가 정해져있습니다.

1번 섬에서부터 시작하여 1번 섬으로 다시 돌아와야 하는데, 이때 최대한 모을 수 있는 보석의 수를 구해야 합니다.

방문했던 다리와 섬은 다시 방문할 수 있고 섬에 있는 보석을 가져가거나 가져가지 않을 수도 있습니다.

 

---

Solution

비트 마스킹 & bfs

각 섬을 지나갈 때 몇 개의 보석을 들고 있어야 하는지, 또 해당 섬에서 보석을 가져가는 게 유리한지 아닌지를 알 수 없기 때문에 모든 탐색이 필요합니다.

이를 위해 비트 마스킹이 필요한데, 각 섬은 최대 100개이고 보석의 수는 최대 14개이므로 100 * 16384(1 << 14)의 2중 배열을 만들어 한 섬에서 들고 지나갈 수 있는 모든 보석의 경우의 수를 확인할 수 있습니다.

저의 경우엔 1번 섬에서 보석을 갖지 않고 시작하는 경우와 1번 섬에 보석이 있다면 보석을 1개 갖고 시작하는 경우 두 가지의 경우를 Queue에 넣고 bfs를 사용했습니다.

모든 bfs가 끝난 후 섬이 1일 때 모든 보석의 경우의 수 중 가장 많은 보석의 수가 정답이 됩니다.

---

Description

• 섬의 인덱스, 보석 수, 보석에 따른 비트 마스킹 수 세 가지를 저장한 Pair라는 자료형을 만들어 bfs에 활용했습니다.
• 다리의 경우엔 ArrayList를 사용하면 반복문을 줄일 순 있지만 섬의 최대 개수가 작기 때문에 복잡성을 줄이기 위해 2중 배열을 사용했습니다.
• 보석의 경우엔 0~최대 보석의 수까지 넘버를 부여해서 비트 마스킹을 활용했습니다.

---

소스 코드

import java.io.*;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Pair{
    int idx;
    int cnt;
    int bit;

    public Pair(int idx, int cnt, int bit) {
        this.idx = idx;
        this.cnt = cnt;
        this.bit = bit;
    }

}

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n, m, k;
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        int last = (1 << k);
        int[][] map = new int[n + 1][1 << k];
        int[][] bridge = new int[n+1][n+1];
        int[] jewel = new int[n+1];
        Arrays.fill(jewel, -1);
        for (int i = 0; i < k; i++) {
            int idx = Integer.parseInt(br.readLine());
            jewel[idx] = i;
        }
        for (int i = 0; i < m; i++) {
            int a, b, c;
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            c = Integer.parseInt(st.nextToken());
            bridge[a][b] = c;
            bridge[b][a] = c;
        }
        int tempBitNum = 0;
        int tempCnt = 0;
        if (jewel[1]!=-1){
            tempBitNum |= (1 << jewel[1]);
            tempCnt++;
        }
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <last ; j++) {
                map[i][j] = -1;
            }
        }
        map[1][tempBitNum] = tempCnt;
        Queue<Pair> q = new LinkedList<>();
        q.add(new Pair(1, tempCnt, tempBitNum));
        q.add(new Pair(1, 0, 0));
        while (!q.isEmpty()) {
            Pair poll = q.poll();
            int idx = poll.idx;
            int cnt = poll.cnt;
            int bitNum = poll.bit;
            for (int i = 1; i <= n ; i++) {
                if(i==idx || bridge[idx][i]==0) continue;
                if (bridge[idx][i] < cnt) continue;
                if (map[i][bitNum] ==-1){
                    map[i][bitNum] = cnt;
                    q.add(new Pair(i, cnt, bitNum));
                }
                int nextCnt = cnt;
                int nextBitNum = bitNum;
                if (jewel[i]!=-1){
                    if ((nextBitNum & (1 << jewel[i])) == 0) {
                        nextCnt++;
                        nextBitNum |= (1 << jewel[i]);
                    }
                }
                if (map[i][nextBitNum]!=-1) continue;
                map[i][nextBitNum] = nextCnt;
                q.add(new Pair(i, nextCnt, nextBitNum));
            }
        }
        int res = 0;
        for (int i = 0; i < last; i++) {
            res = Math.max(res, map[1][i]);
        }
        bw.write(res+"\n");
        bw.flush();
        br.close();
        bw.close();
    }
}