[백준] 2001번 보석 줍기

문제 설명

• https://www.acmicpc.net/problem/2001
• Gold 1

문제 풀이

• 비트마스킹을 통한 BFS를 통해 풀이가 가능하다.
• 방문 체크는 아래 배열을 통해서 진행한다.

  visited[N][bitmasking] : N번 노드를 특정 보석 조합(bitmasking)을 들고 방문 했는지 여부

• 해당 배열을 통해 방문 체크를 하고 BFS를 통해 특정 노드의 보석을 줍는 케이스, 줍지 않는 케이스를 모두 큐에 넣으면서 진행하면 된다.
• 다만, 문제의 예제처럼 시작 노드에 보석이 존재하는 케이스를 위해 0번 노드를 만들어 1번노드와 이어주고 0번을 시작노드처럼 진행하면 예외처리가 가능하다.

소스 코드 (JAVA)

import java.io.*;
import java.util.*;

class Main {

    static BufferedReader br;
    static BufferedWriter bw;

    static class Point {
        int a, b;

        public Point(int a, int b) {
            this.a = a;
            this.b = b;
        }
    }

    static int N, M, K;
    static int[] targetInfo;  // 해당 섬에 존재하는 보석 번호
    static List<List<Point>> map = new ArrayList<>(); // 지도 정보

    static int bitMaskToCnt(int bitMasking) {
        int cnt = 0;
        while (bitMasking != 0) {
            bitMasking = bitMasking & (bitMasking - 1);
            cnt++;
        }
        return cnt;
    }

    static void solve() throws IOException {
        // BFS 사용할 데이터 초기화
        boolean[][] visited = new boolean[N+1][1<<K];
        Queue<Point> q = new ArrayDeque<>();
        q.add(new Point(0, 0));
        visited[0][0] = true;

        while(!q.isEmpty()) {
            Point cur = q.poll();

            for (int i = 0; i < map.get(cur.a).size(); i++) {
                int nA = map.get(cur.a).get(i).a;
                int nB = map.get(cur.a).get(i).b;

                // 1. 그냥 지나감
                // 현재 무게로 지나갈 수 있는 경우
                // 해당 조합으로 다음 노드를 방문한적 없는 경우
                if (bitMaskToCnt(cur.b) <= nB && !visited[nA][cur.b]) {
                    visited[nA][cur.b] = true;
                    q.add(new Point(nA, cur.b));
                }

                // 2. 현재 위치 보석 존재하는 경우 보석을 담음
                // 변화된 무게로 지나갈 수 있는 경우
                // 변화된 조합으로 다음 노드를 방문한적 없는 경우
                int nMasking = cur.b | (1 << (targetInfo[cur.a]));
                if (targetInfo[cur.a] != -1 && bitMaskToCnt(nMasking) <= nB && !visited[nA][nMasking]) {
                    visited[nA][nMasking] = true;
                    q.add(new Point(nA, nMasking));
                }
            }
        }

        int result = 0;
        for (int i = 0; i < (1<<K); i++) {
            if (!visited[0][i]) continue;
            result = Math.max(result, bitMaskToCnt(i));
        }
        bw.write(result + "\n");
        bw.flush();
    }


    public static void input() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        targetInfo = new int[N+1];
        Arrays.fill(targetInfo, -1);
        for (int i = 0; i <= N; i++)
            map.add(new ArrayList<>());
        for (int i = 0; i < K; i++)
            targetInfo[Integer.parseInt(br.readLine())] = i;
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            map.get(a).add(new Point(b, c));
            map.get(b).add(new Point(a, c));
        }
        map.get(0).add(new Point(1, 987654321)); // 가상의 0번 노드를 만들어줌 
        map.get(1).add(new Point(0, 987654321));
    }

    public static void main(String[] args) throws IOException {
        input();
        solve();
    }
}

/**
 * - N : 섬 개수 ( <= 100)
 * - M : 다리 개수 ( <= 1000)
 * - K : 보석이 존재하는 섬 개수 ( <= 14)
 * - 1번 섬에서 출발하여 최대한 많은 보석을 줍고 1번 섬으로
 * - 다리가 무너지지 않는 선에서 보석을 주워야 한다.
 * - 섬을 지날 때 보석을 줍지 않을 수 있다.
 *
 * N M K
 * k개줄 보석 섬
 * m개줄 다리 정보
 *
 * - 주울 수 있는 보석의 최대 개수
 * - BFS로 진행하되 해당 노드의 도달 했을 때 최대값보다 작으면 넘긴다.
 * - DP[N][bitmasking] : N노드를 bitmasking 정보대로 들고 방문 했는지 여부
 * - bitmaskin
 */