[백준 / BOJ] 1194번 : 달이 차오른다, 가자. - JAVA

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

1194번: 달이 차오른다, 가자.

BFS

"최소 거리"를 구해야 하기 때문에 BFS를 사용해야 한다. 처음에는 열쇠 조건을 배열로 만들려고 DFS로 구현했었는데 시간 초과가 나왔다. BFS로 바꾸니까 통과할 수 있었다.

 

방문 체크

처음에 DFS를 사용했던 게 방문 체크에 조건이 복잡했기 때문이다. 만일 단순히 v[N][M]으로 체크를 해준다면, 막다른 길에 열쇠가 있을 때 열쇠를 갖고도 다시 못 돌아오는 경우가 생긴다. 따라서 '어떤 열쇠를 갖고 있는가'를 방문 체크 조건에 넣어줘야 한다. 배열로 key를 저장할 수도 있지만, BFS로 구현할 때 배열을 두면 너무 복잡하기 때문에 비트 마스킹으로 구현했다. 즉 Queue에 넣는 int[] 배열의 구성은 다음과 같다.

Queue의 원소 : {r, c, key, cnt}

key는 갖고있는 열쇠를 비트마스킹으로 저장한 변수이다. 열쇠를 추가하거나, 갖고 있는지 확인할 때는 다음과 같이 연산한다.

// 'c' 열쇠를 추가하는 경우
key |= (1 << 'c' - 'a');

// 'c' 열쇠를 갖고 있는지 확인하는 경우
if((key & (1 << 'c' - 'a') > 0)

이 key 값은 최대 111111로 63이다. 따라서 방문체크 배열을 v[N][M][64]로 두고 풀 수 있었다.

 

전체 코드

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

// 시간 : 104ms
// 메모리 : 14344KB
public class Main {

	static int[] dr = {-1,0,1,0};
	static int[] dc = {0,-1,0,1};
	static int N;
	static int M;
	static int min;
	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());
		
		char[][] map = new char[N][M];
		Queue<int[]> que = new LinkedList<>();
		boolean[][][] v = new boolean[N][M][64];
		for (int i = 0; i < N; i++) {
			String str = br.readLine();
			for (int j = 0; j < M; j++) {
				map[i][j] = str.charAt(j);
				if(map[i][j] == '0') {
					que.offer(new int[] {i, j, 0, 0});
					v[i][j][0] = true;
					map[i][j] = '.';
				}
			}
		}

		int time = -1;
		while(!que.isEmpty()) {
			int[] cur = que.poll();
			if(map[cur[0]][cur[1]] == '1') {
				time = cur[3];
				break;
			}
			
			for (int d = 0; d < 4; d++) {
				int nr = cur[0] + dr[d];
				int nc = cur[1] + dc[d];
				
				if(nr >= N || nc >= M || nr < 0 || nc < 0) continue;
				if(v[nr][nc][cur[2]] || map[nr][nc] == '#') continue;
				if(map[nr][nc] >= 'A' && map[nr][nc] <= 'F') {
					if((cur[2] & (1 << map[nr][nc] - 'A')) > 0) {
						v[nr][nc][cur[2]] = true;
						que.offer(new int[] {nr, nc, cur[2], cur[3] + 1});
					}
				} else if(map[nr][nc] >= 'a' && map[nr][nc] <= 'f') {
					v[nr][nc][cur[2]] = true;
					que.offer(new int[] {nr, nc, cur[2] | (1 << map[nr][nc] - 'a'), cur[3] + 1});
				} else {
					v[nr][nc][cur[2]] = true;
					que.offer(new int[] {nr, nc, cur[2], cur[3] + 1});
				}
			}
		}
		System.out.println(time);
	}
}