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

문제 설명

• https://www.acmicpc.net/problem/1194
• 2차원 배열을 탐색합니다.
• 특정 조건에 따라 길을 지나가며 시작위치에서 도착위치까지 가는 이동횟수를 구하는 문제입니다.
  • 특정조건은 다음과 같습니다.
    • 0에서 출발해서 1에 도착해야 합니다.
    • 벽은 통과하지 못합니다.
    • 문은 열쇠를 가지고 있어야 통과할 수 있습니다.

접근법

• 2차원 배열에서 최단경로를 구해야 하기 때문에 BFS를 활용해야 합니다.
• 방문처리를 3차원 배열로 진행해야 합니다.
  • v[i][j][k]는 k상태로 (i,j)를 방문했는지를 나타냅니다.
    • 이 문제는 x열쇠 없이 (i,j)를 방문하는 것과 x열쇠를 가지고 (i,j)를 방문하는 것이 다르기 때문에 3차원 배열이 필요합니다.
• 비트마스킹 계산을 활용하면 편리합니다.
  • 비트마스킹 설명은 여기를 참고해 주세요.
  • 1 << n : n번째 값이라는 의미입니다.
  • x & (1 << n) : x의 n번째 값이 0(false)면 0을 반환합니다. // n번째 값이 1(true)일 때 1을 반환하는 건 아닙니다. 1<<n을 반환힙니다.
  • x | (1 << n) : x의 n번째 값을 1(true)로 변환합니다.
  • a열쇠를 0번째 자릿수, f열쇠를 5번째 자릿수로 표현했을 때 그 일부는 다음과 같습니다.

// fedcba
000000 // 아무열쇠도 들고있지 않다
111111 // 모든 열쇠를 다 가지고 있다
000001 // a열쇠만 가지고 있다
010010 // e와b 열쇠를 가지고 있다

pseudocode

BFS{
	3차원 방문배열 생성
    큐 생성
    큐에 시작값 추가
	while(큐가 빌 때가지){
        큐에서 현재위치를 꺼냄
        if(지금 서있는 위치가 1이면) return cnt;
        if(배열을 벗어나면) continue;
        if(이미 동일한 조건으로 방문한 곳이면) continue;
        if(문인데 알맞은 열쇠를 가지고 있지 않으면) continue;
        else{
            if(현재 위치가 열쇠면){열쇠값 갱신}
            현재위치를 방문처리 후 큐에 삽입
        }
	}
}

정답

import java.io.*;
import java.util.*;

class Main {
	static int N, M;
	static int[] dx = { 0, -1, 0, 1 };
	static int[] dy = { -1, 0, 1, 0 };

	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[][] board = new char[N][M];
		for (int i = 0; i < N; i++) {
			board[i] = br.readLine().toCharArray();
		}

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (board[i][j] == '0') {
					int[] start = { i, j, 0 };
					board[i][j] = '.';
					System.out.println(BFS(start, board));
					break;
				}
			}
		}
	}

	public static int BFS(int[] start, char[][] board) {
		boolean[][][] v = new boolean[N][M][64];
		v[start[0]][start[1]][start[2]] = true;
		Queue<int[]> q = new LinkedList<int[]>();
		q.add(start);
		int cnt = 0;
		while (!q.isEmpty()) {
			int size = q.size();
			while (--size >= 0) {
				int[] now = q.poll();
				if (board[now[0]][now[1]] == '1')
					return cnt; // 탈출
				for (int d = 0; d < 4; d++) {
					int nx = now[0] + dx[d];
					int ny = now[1] + dy[d];
					if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue; // 배열범위 밖
					else if (board[nx][ny] == '#') continue; // 벽
					else if (v[nx][ny][now[2]]) continue; // 방문했으면
					else if (Character.isUpperCase(board[nx][ny]) && (now[2] & (1 << (board[nx][ny] - 'a'))) == 0) continue; // 문을 만났는데 열쇠가 없으면
					else { 
						int key = now[2];
						if (Character.isLowerCase(board[nx][ny])) { // 열쇠를 먹으면
						key = (now[2] | (1 << (board[nx][ny] - 'a')));
						}
						int[] next = { nx, ny, key };
						q.add(next);
						v[nx][ny][now[2]] = true;
					}

				}

			}
			cnt++;
		}
		return -1;
	}
}