[백준 Java] 1194 달이 차오른다 가자

문제 링크

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

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static int N, M;
	static char[][] map;

	static class Pos {
		int x, y, cnt, key;

		public Pos(int x, int y, int cnt, int key) {
			this.x = x;
			this.y = y;
			this.cnt = cnt;
			this.key = key;
		}	
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer tokens = new StringTokenizer(br.readLine());
		N = Integer.parseInt(tokens.nextToken());
		M = Integer.parseInt(tokens.nextToken());
		map = new char[N][M];

		int startX = 0, startY = 0;
		String temp;
		for (int i = 0; i < N; i++) {
			temp = br.readLine();
			for (int j = 0; j < M; j++) {
				map[i][j] = temp.charAt(j);
				if (map[i][j] == '0') {
					startX = i; // 시작 위치 설정
					startY = j;
				}
			}
		} // end input

		bfs(startX, startY);

	}

	static int[] dr = { -1, 1, 0, 0 };
	static int[] dc = { 0, 0, -1, 1 };

	private static void bfs(int startX, int startY) {
		Queue<Pos> q = new ArrayDeque<>();
		boolean[][][] v = new boolean[64][N][M]; // a~f까지 키 주웠는지 확인 배열
		q.add(new Pos(startX, startY, 0, 0)); // 첫번째 출발 위치 넣음. 키는 아무것도 없음
		map[startX][startY] = '.';

		while (!q.isEmpty()) {
			Pos cur = q.poll();

			for (int d = 0; d < 4; d++) {
				int nx = cur.x + dr[d];
				int ny = cur.y + dc[d];

				if (!isRange(nx, ny) || map[nx][ny] == '#' || v[cur.key][nx][ny])
					continue; // 범위 벗어나거나, 벽이거나, 현재키로 방문했으면 다른방향
				
				if(map[nx][ny]=='1') {
					System.out.println(cur.cnt+1);
					return;
				}
				
				if (map[nx][ny] == '.') { // 갈 수 있으면 다음 방향 넣음
					v[cur.key][nx][ny] = true;
					q.add(new Pos(nx, ny, cur.cnt+1, cur.key));
				}
				if (map[nx][ny] >= 'a' && map[nx][ny] <= 'f') {// 소문자라면
					int gainKey = 1 << (map[nx][ny] - 'a');
					gainKey = cur.key | gainKey; // or 연산으로 현재 얻은 키 갱신

					if (!v[cur.key][nx][ny]) { //현재 키들로 방문하지 않았을 때 방문처리해줌 ->다시 갈 필요 없기 때문
						v[cur.key][nx][ny] = true;
						v[gainKey][nx][ny] = true;
						q.add(new Pos(nx, ny, cur.cnt + 1, gainKey));
					}
				}
				if (map[nx][ny] >= 'A' && map[nx][ny] <= 'F') {
					int checkKey = 1 << (map[nx][ny]-'A');
					if((cur.key & checkKey) > 0) { //키와 문의 대응이 1이상 존재한다면
						v[cur.key][nx][ny] = true;
						q.add(new Pos(nx, ny, cur.cnt+1, cur.key));
					}
				}

			}
		}
		System.out.println(-1);
		return;
	}

	private static boolean isRange(int x, int y) {
		if (x < 0 || y < 0 || x >= N || y >= M)
			return false;
		return true;
	}
}

bfs로 풀었는데 비트마스킹으로도 풀 수 있다!