[백준][BOJ-2001][JAVA] 보석줍기

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

2001번: 보석 줍기

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

public class Main {
	static int N,M,K,max;
	static int[] islandGems;
	static int[][] islandData;
	
	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());
		
		islandGems = new int[K];
		islandData = new int[N][N];
		
		for(int i=0; i<K; i++) {
			islandGems[i] = Integer.parseInt(br.readLine()) -1;
		}
		
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			int num = Integer.parseInt(st.nextToken());
			
			islandData[x-1][y-1] = num;
			islandData[y-1][x-1] = num;
		}
		
		bfs();
		
		System.out.println(max);
	}

	private static void bfs() {
		Queue<Vertax> qu = new LinkedList<Vertax>();
		boolean[][] visited = new boolean[N][1<<16];
		
		boolean first = false;
		int num = isCheckedGem(0) + 1;
		
		// 첫번째 보석도 잡고 가는 경우 아닌 경우
		qu.offer(new Vertax(0, 0, 0));
		visited[0][0] = true;
		if(num != 0) {
			qu.offer(new Vertax(0, 1, num));
			visited[0][num] = true;
			max = 1;
		}
		
		while(!qu.isEmpty()) {
			int size = qu.size();
			for(int i =0; i<size; i++) {
				Vertax vt = qu.poll();
				int no = vt.no;
				int gemCnt = vt.gemCnt;
				int gemCheck = vt.gemCheck;
				
				// 1번 도착시
				if(vt.no == 0 && vt.gemCnt != 0 && first) {
					max = Math.max(max, vt.gemCnt);
					continue;
				}
				
				for(int j=0; j<N; j++) {
					if(islandData[no][j] == 0 || gemCnt > islandData[no][j] ||visited[j][gemCheck]) continue;
					
					// 보석 줍지 않는 경우
					qu.offer(new Vertax(j,gemCnt,gemCheck));
					visited[j][gemCheck] = true;
				
					// 보석 줍는 경우
					int gemNumber = isCheckedGem(j);
					if(gemNumber != -1){
						// 이미 보석을 들고 있는지 체크
						if((gemCheck & (1 << gemNumber)) == 0) {
							// 보석 추가
							int temp = gemCheck | (1 << gemNumber);
							qu.offer(new Vertax(j,gemCnt+1,temp));
							visited[j][temp] = true;
						}
					}
					
				}
			}
			
			// 처음 체크
			first = true;
		}
	}
	
	private static int isCheckedGem(int cur) {
		for(int i=0; i<islandGems.length; i++) {
			if(islandGems[i] == cur) return i;
		}
		return -1;
	}
}

class Vertax{
	int no;
	int gemCnt;
	int gemCheck; 
	public Vertax(int no, int gemCnt, int gemCheck) {
		super();
		this.no = no;
		this.gemCnt = gemCnt;
		this.gemCheck = gemCheck;
	}
}

정리

비트 마스킹만 안다면 풀 수 있는데 익숙하지 않아서 어렵네요

로직을 살펴보면 우선 저는 BFS로 풀었습니다.

1. 현재 시작섬이 보석을 가지고 있는지 확인 Queue에 넣어주고 방문 체크를 해준다. 
2. Queue에서 꺼내서 현재 섬에서 다른 섬으로 갈 수 있는지, 방문되어 있는지, 다리를 건널 수 있는지 체크한다.
3. 보석을 줍지 않는 경우도 있기때문에 그대로 Queue에 넣어준다.
4. 그리고 가려고 하는 섬에 보석이 있는지 체크한다. 비트 마스킹으로 현재 Data에 보석을 가지고 있는지 체크 그리고 똑같이 OR연산으로 추가해주고 방문 체크해준다.
5. 2번 문항으로 돌아가 Queue에서 꺼내면서 해당 섬이 시작 섬이라면 최댓값을 구해준다.