[BOJ 1194] 달이 차오른다, 가자. (Java)

BOJ 1194 달이 차오른다, 가자.

문제풀이

항상 느끼는 것인데 BFS에서 방문체크는 활용이 무궁무진한 것 같다.

• 가장 기초적인 방문체크는 해당 좌표에 이전에 방문한 적이 있는지 확인한다.
• 다음으로 많이 사용되는 것은 특정 시간에 해당 좌표를 방문한 적 있는가
• 이 문제에서는 특정 상태에 해당 좌표를 방문한 적 있는가

어떤 열쇠를 가지고 있는 상태에서 이 지점을 방문했는지 체크하는 것이 이 문제의 핵심이다. 이 때 열쇠의 상태를 자료구조를 통해 나타낸다면 메모리 또는 시간이 부족할 것이다. 비트마스킹을 사용하면 현재 상태를 간단하고 빠르게 나타낼 수 있다.

이 문제에서는 키를 6개 가지고 있으므로 2^6 개의 경우를 가지고 있다. 따라서 방문체크 배열은 visited[N][M][64]로 나타낼 수 있다.

• 키의 상태는 2진법으로 나타낼 수 있으며 각 비트는 특정 열쇠를 나타낸다.
  • 오른쪽에서 왼쪽으로 a ~ f의 열쇠를 나타낸다.
  • 000001(2) 열쇠 a를 가지고 있음
  • 100000(2) 열쇠 f를 가지고 있음
• 열쇠에 도달했을 때 해당 키를 추가하려면 | 연산을 사용한다.
  • a열쇠에 도달했을 때 &연산으로 먼저 이미 가지고 있는지 확인한다.
  • 없다면 000001(2)와 현재 열쇠 상태를 | 연산하여 합쳐준다.
• 문에 도달했을 때 해당 키를 가지고 있는지 확인하기 위해서는 & 연산을 사용한다.
  • A문에 도달했을 때 필요한 열쇠는 a이므로 000001(2)와 현재 열쇠 상태를 &연산 했을 때 가지고 있다면 000001(2)를 리턴할 것이다.

비트마스킹은 어려운 것이라는 선입견을 가지고 안해야지! 했었는데 굉장히 유용하고 오히려 문제를 쉽게 만들어주는 것 같다. 특정 상태를 쉽게 저장하고 관리할 필요가 있을 때 비트마스킹을 애용해야겠다.

구현코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	
	static class Node {
		int r, c, k;
		
		Node(int r, int c, int k){
			this.r = r;
			this.c = c;
			this.k = k;
		}
	}
	
	static Queue<Node> q;
	static int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
	static char[][] map;
	static boolean[][][] visited;
	static int N, M;
	
	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());
		
		q = new LinkedList<>();
		map = new char[N][M];
		visited = new boolean[N][M][64];
		
		for(int r = 0 ; r < N ; ++r) {
			char[] line = br.readLine().toCharArray();
			for(int c = 0 ; c < M ; ++c) {
				map[r][c] = line[c];
				
				if(map[r][c] == '0') {
					q.offer(new Node(r, c, 0));
					visited[r][c][0] = true;
					map[r][c] = '.';
				}
			}
		}
		
		System.out.println(bfs());
	}

	private static int bfs() {
		int time = 0;
		
		while(!q.isEmpty()) {
			int size = q.size();
			time++;
			
			for(int i = 0 ; i < size ; ++i) {
				Node cur = q.poll();
				int r = cur.r;
				int c = cur.c;
				int k = cur.k;
				
				for(int d= 0 ; d < 4 ; ++d) {
					int nr = r + dir[d][0];
					int nc = c + dir[d][1];
					int nk = k;
					
					if(nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
					if(visited[nr][nc][k] || map[nr][nc] == '#') continue;
					
					if(map[nr][nc] == '1') return time;
					
					else if(map[nr][nc] >= 'a' && map[nr][nc] <= 'z') {
						int ck = 1 << (map[nr][nc] - 'a');
						if((k & ck) != ck) nk |= ck;
					} else if(map[nr][nc] >= 'A' && map[nr][nc] <= 'Z') {
						int cd = 1 << (map[nr][nc] - 'A');
						if((k & cd) != cd) continue;
					}

					q.offer(new Node(nr, nc, nk));
					visited[nr][nc][k] = true;
				}
			}
		}
		return -1;
	}
}