[BOJ-2001][비트마스킹] 보석줍기 -Java

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

2001번: 보석 줍기

package algo;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class boj_2001_보석도둑 {
	static class BridgeInfo{
		int end, weight;
		public BridgeInfo(int end, int weight) {
			this.end = end;
			this.weight = weight;
		}
	}
	static List <BridgeInfo> []bridgeInfo;
	static int isGemsIsland[]= new int[101];
	static boolean [][]visited =  new boolean [1<<16][101];
	static int N,M,K, result;
	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());
		result=Integer.MIN_VALUE;
		
		bridgeInfo=new List[N+2];
		
		for(int i=0; i<=N+1; i++) { // 다리의 정보 저장
			bridgeInfo[i] =  new ArrayList<>();
		}
		
		Arrays.fill(isGemsIsland, -1);
		for(int i=0; i<K; i++) { // 보석이 있는 섬 표시
			int gemIndex = Integer.parseInt(br.readLine());
			isGemsIsland[gemIndex]=i;
		}
		
		for(int i=0; i<M; i++) {
			st =  new StringTokenizer(br.readLine());
			int start=Integer.parseInt(st.nextToken());
			int end=Integer.parseInt(st.nextToken());
			int weight=Integer.parseInt(st.nextToken());
			
			bridgeInfo[start].add(new BridgeInfo(end, weight));
			bridgeInfo[end].add(new BridgeInfo(start, weight));
		}
		bridgeInfo[1].add(new BridgeInfo(1, 1000));
		
		solve(1,0,0);
		System.out.println(result);
		
		
		
	}
	private static void solve(int curIsland, int curState, int curGemCnt) {
		visited[curState][curIsland]=true;
		
		if(curIsland==1) {
			result=Math.max(curGemCnt, result);
		}
		
		boolean isGemCurIsland = (isGemsIsland[curIsland]!=-1) ? true : false;		
		int nextState = (curState | (1<<isGemsIsland[curIsland]) ); //상태 미리 바꿔주고

		int size=bridgeInfo[curIsland].size();
		
		for(int i=0; i<size; i++) {
			BridgeInfo info = bridgeInfo[curIsland].get(i);
			
			//아직 방문하지 않았고, 다리무게가 버틸 수 있다면 
			if(!visited[curState][info.end] && info.weight>=curGemCnt) {
				solve(info.end,  curState, curGemCnt); 
			}
			
			if(isGemCurIsland) { //보석이 있으면 보석 줍고 가기 
				if((curState & (1<<isGemsIsland[curIsland]))>0) continue;
				
				if(info.weight<curGemCnt+1 || visited[nextState][info.end]) continue; 
				solve(info.end, nextState, curGemCnt+1);
			}
			
		}
	}

}

소요시간 : 1시간 30분

 

비트마스킹 진짜 어렵네여...

 

이 문제에서 제가 핵심이라고 생각한 부분은 같은 state를 가진 섬에 2번이상 접근할 필요가 없다는 것입니다.

예시로 주어진 문제를 손으로 직접 해보시면 위의 말이 무슨말인지 이해하실 수 있으실거라고 생각합니다.

 

로직을 살펴보면 우선 저는 DFS를 이용해서 풀었습니다.

1. 현재 섬이 보석을 가지고 있는지 확인

2. 만약 보석을 가지고 있다면 비트 마스킹을 통해 state를 변경시키고 dfs를 다시 불러줍니다.

   이때 무게가 초과한다면 가지 못합니다.

3. 만약 보석을 가지고 있지 않다면  visited처리만 해주고 다음으로 넘겨줍니다.