[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();
	}
}