[백준] 9328 열쇠 - 시뮬레이션 + 구현 + BFS(너비우선탐색) + 비트마스크(BitMask) JAVA

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

9328번: 열쇠

코드설명

시뮬레이션 + 구현 + BFS(너비우선탐색) + 비트마스크(BitMask) 문제입니다.

 

이번 문제에서 유의해야할점은, 최단거리를 구하는것이 아닌 훔칠 수 있는 문서의 최대 개수를 구하는 것입니다.

처음에는 최단거리를 구하는 줄알고, BFS에서 여러 경우를 고려하며 어떻게 열쇠를 가진상태에서 최단거리를 구하지라는 고민을 했었기에 각 Class마다 Key값을 두고 가지고 있는 키의 종류와 비교하며 진행하려했지만, 그렇게 할경우 Visited배열에 각 키값을 가지고있는경우의수를 모두 저장하며 진행해야하고, 이 문제가 원하는 값을 빠르게 도출하지 못합니다.

 

단순히 훔칠 수 있는 문서의 최대개수를 구하는경우, 문제가 훨씬 간단해집니다.

또한 처음에는 평면도에서 빌딩의 가장자리를 모두 돌면서 따로 BFS를 수행하거나 각 가장자리의 값들을 모두 Queue에 넣어서 실행하기보다는 빌딩의 크기를 늘려주어서 처리하면 됩니다.

이때 처음에는 CharToArrays를 사용해서 w+2 만큼 값을 넣어주지않고 w만큼 값을 넣어서 오류가 IndexOutof Error를 발견햇었습니다. 반복문으로 입력을 바꾸어서 처리하여 해결했습니다.

 

이번 문제를 풀며 문제의 접근을 최대한 간단하게 생각하는 방법을 생각하여야 코드의 복잡도가 훨씬 줄어들 수 있다는 것을 다시 느꼈습니다.

 

또한 구현중에 Visited[nr][nc]에 Key값을 저장해두는데 이를 통해 같은 이전에 같은 키값을 들고서 들어왔던경우는 다시 들어오지 않도록 합니다. 만약 새로운 Key값이라면 다시 방문하여 방문하지 못했던 곳을 방문할 수 있습니다.

이떄 Key값 같은경우 key[ 26 ] 으로 처리해도 되지만, 비트마스크도 활용해보고 싶어 사용했습니다.

 

만약 Visited[nr][nc][Keys] 로 하여 처리했다면, Key값이 비트마스킹을 거치며 2^26 값의 경우의 수가 나오기에 Overflow가 나올것입니다. 

 

문제가 원하는 것이 무엇인지에 대하여 생각하여 간단하게 해결, 복잡도를 낮추는 방법에 대해서 고민해보면 좋을 문제입니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
	
	public static int N, M, K, T;
	public static int answer = 0;
	public static int[] arr;
	public static char[][] map;
	public static int[] dx = {-1,1,0,0};
	public static int[] dy = {0,0,-1,1};
	public static int h = 0, w = 0;
	public static int[][] visited;
	public static int key;
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	
    	T = Integer.parseInt(st.nextToken());
    	
    	while(T-- > 0) {
    		answer = 0;
    		st = new StringTokenizer(br.readLine());
    		h = Integer.parseInt(st.nextToken());
    		w = Integer.parseInt(st.nextToken());
    		map = new char[h+2][w+2];
    		for(int i=1;i<=h;i++) {
    			st = new StringTokenizer(br.readLine());
    			String input = st.nextToken();
    			for(int j=1; j<=w;j++) {
    				map[i][j] = input.charAt(j-1);	
    			}
				
    		}
    		key = 0;
    		st = new StringTokenizer(br.readLine());
    		String inputKey = st.nextToken();
    		for(int i=0;i<inputKey.length();i++) {
    			key |= (1 << inputKey.charAt(i) - 'a'); //비트마스킹.
    		}
    		BFS();
    		System.out.println(answer);
    	}
	}
	
	public static void BFS() {
		Queue<Node> q = new LinkedList<>();
		//Map의 Size가 map[h+2][w+2] 이므로 아무데서나 시작해도 괜찮다.
		visited = new int[h+2][w+2];
		visited[0][0] = key;
		q.offer(new Node(0, 0));
		while(!q.isEmpty()) {
			Node temp = q.poll();
			for(int dir = 0; dir < 4; dir++) {
				int nr = temp.r + dx[dir];
				int nc = temp.c + dy[dir];
				
				if(nr < 0 || nr > h + 1 || nc < 0 || nc > w + 1 ) continue;
				if(map[nr][nc] == '*') continue;
				
				if(visited[nr][nc] == key) continue;
				if(map[nr][nc] >= 'A' && map[nr][nc] <= 'Z') {
					boolean flag = (key & (1 << map[nr][nc] - 'A')) > 0; //만약 0 이라면 key가 없는것입니다.
					if(flag == false) { //만약 key가 없는경우라면 continue
						continue;
					}
				}
				else if(map[nr][nc] >= 'a' && map[nr][nc] <='z') { //만약 소문자라면 key값입니다.
					key |= (1 << map[nr][nc] - 'a');
				}
				else if(map[nr][nc] =='$')
					answer += 1;
				
				map[nr][nc] = '.'; //방문한곳은 . 로 바꿔놓습니다.
				visited[nr][nc] = key;
				q.offer(new Node(nr, nc));
			}
		}
	}
}
 
 
class Node{
	int r;
	int c;
	public Node(int r, int c) {
		this.r = r;
		this.c = c;
	}
}