백준 2001 (보석 줍기) - java

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

2001번: 보석 줍기

문제

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

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

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

 

유형 : 그래프 탐색 + 비트 마스킹

 

접근 방식

• 1번 정점의 보석은 마지막에 줍는다.
• 방문했던 정점을 다시 방문할 수 있기 때문에 방문 배열을 i번째 정점에 j의 보석 정보 ( 비트마스킹 ) 사용
• 해당 정점에 보석의 수로 방문 못하는 경우 고려 !!!!

전체 코드

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

public class Main {

    static int n = 0;
    static int m = 0;
    static int k = 0;

    static int max = 0;
    static ArrayList<Edge>[] graph;
    static int[] isJ;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        isJ = new int[n+1];
        graph = new ArrayList[n+1];

        for(int i=1 ; i<=n ; i++){
            graph[i] = new ArrayList<>();
        }

        for(int i = 1 ; i <= k ;i++){
            int cur = Integer.parseInt(br.readLine());

            isJ[cur] = i; // 해당 정점에 보석 정보 기입
        }

        for(int i = 1 ; i <= m ; i++){
            st = new StringTokenizer(br.readLine()," ");

            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            graph[v1].add(new Edge(v2,c));
            graph[v2].add(new Edge(v1,c)); // 그래프 생성
        }

        boolean[][] v = new boolean[n+1][1 << (k + 1)]; // i번째 정점에 해당 보석 정보

        Queue<Edge> q = new ArrayDeque<>();
        q.add(new Edge(1,0));

        v[1][0] = true;

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

            if(cur.v == 1){
                int plus = isJ[1] > 0 ? 1 : 0; // 1번 정점의 보석은 마지막에 줍는다

                if(plus == 1){
                    if((cur.c & 1 << 1) != 0){
                        max = Math.max(max,countOne(cur.c)); // 이미 1번껄 먹었다면
                    }else{
                        max = Math.max(max,countOne(cur.c) + 1); // 안먹었다면
                    }
                }else{
                    max = Math.max(max,countOne(cur.c) + plus); // 1번 정점에 보석이 없다면
                }
            }

            for(Edge next : graph[cur.v]){

                int count = countOne(cur.c);

                if(count > next.c)
                    continue;
                
                // 보석이 있는 정점이라면
                if(isJ[next.v] > 0){
                    if(count < next.c){
                        // 줍거나 안줍거나
                        if(!v[next.v][cur.c | 1 << isJ[next.v]]){
                            v[next.v][cur.c | 1 << isJ[next.v]] = true;
                            q.add(new Edge(next.v,cur.c | 1 << isJ[next.v]));
                        }

                        if(!v[next.v][cur.c]){
                            v[next.v][cur.c] = true;
                            q.add(new Edge(next.v , cur.c));
                        }

                    }else if(count == next.c){
                        // 안주어야 함
                        if(!v[next.v][cur.c]){
                            v[next.v][cur.c] = true;
                            q.add(new Edge(next.v , cur.c));
                        }
                    }

                }else{
                    if(!v[next.v][cur.c]){
                        v[next.v][cur.c] = true;
                        q.add(new Edge(next.v , cur.c));
                    }
                }

            }
        }


        System.out.println(max);
        br.close();
    }

    static int countOne(int num){
        int count = Integer.bitCount(num);

        return count;
    }
}
class Edge{
    int v;
    int c;

    Edge(int v,int c){
        this.v = v;
        this.c = c;
    }
}