[백준 / Java] 1194번: 달이 차오른다, 가자 (골드1)

문제 풀이 날짜: 2023.09.26
포스트 작성일: 2023.09.30

 

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

 

문제 출처

백준 온라인 저지 1194번: 달이 차오른다, 가자 (골드1)

 

키워드

BFS, 비트마스킹

 

풀이 접근법 

• 열쇠의 구현 : f(소문자)에 방문한 적 있다면 그 후에 F(대문자)에 방문할 수 있다.
• 열쇠를 얻고 되돌아가야 하기 때문에, 방문했던 곳을 다시 갈 수 있어야 한다 ⇒ visited 처리가 애매해짐
  
  • 따라서 visited 배열을 3차원 배열로 선언해준다.

• 1번 테케의 경우, f를 얻고 F를 큐에 “다시” 넣을 때까지 F가 열리면 안 된다.
  • 즉, key의 존재 여부에 따라 맵이 각기 다른 상태를 보존해야 한다.
  • 따라서 6가지의 키를 각각 가지고 있는지/가지지 않았는지를 구별할 수 있도록 3차원 배열의 첫 번째 인덱스 크기를 2^6 = 64로 초기화 해준다.
  • 6가지 키의 소지 여부는 비트마스킹으로 기록한다. (예: a번 키와 c번 키를 가지고 있다면 000101)
• BFS 호출은 다음의 세 가지 분기로 나누어서 한다
  • 1. 그냥 지나갈 수 있는 길을 탐색하는 경우
  • 2. 열쇠가 있는 곳을 탐색하는 경우
  • 3. 문이 있는 곳을 탐색하는 경우

• 궁극적으로 이 문제에서 물어보는 포인트 : 서로 다른 상태 64개에 대해서 각각의 matrix 정보를 기록할 수 있는가?

 

코드

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

public class Main {

	private static final char START = '0';
	private static final char END = '1';
	private static final char BLANK = '.';
	private static final char WALL = '#';
	
	private static int N;
	private static int M;
	
	private static char[][] matrix; //출발지, 도착지, 열쇠 등을 기록
	private static boolean[][][] visited; //지나갈 수 있는지/없는지를 기록
	
	private static int[] dr = {0, 1, -1, 0};
	private static int[] dc = {1, 0, 0, -1};

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String[] temp = br.readLine().split(" ");
		
		N = Integer.parseInt(temp[0]);
		M = Integer.parseInt(temp[1]);
		
		matrix = new char[N][M];
		visited = new boolean[64][N][M]; //0: 아무 키도 없음 / 1: a번 키만 가지고 있음 / ...
		
		int startR = 0;
		int startC = 0;
		for(int i = 0; i < N; i++) {
			String line = br.readLine();
			for(int j = 0; j < M; j++) {
				matrix[i][j] = line.charAt(j);
				
				if(matrix[i][j] == START) {
					startR = i;
					startC = j;
				}
			}
		}
		
		int result = BFS(startR, startC);
		
		System.out.println(result);
	}
	
	public static int BFS(int startR, int startC) {
		Queue<Node> queue = new ArrayDeque<>();
		
		visited[0][startR][startC] = true;
		queue.add(new Node(startR, startC, 0, 1 >> 6));
		
		while(!queue.isEmpty()) {
			Node n = queue.poll();
			int width = n.width;
			int currKey = n.key;
			
			if(matrix[n.row][n.col] == END) { return width; }
			
			int nr = 0;
			int nc = 0;
			for(int i = 0; i < dr.length; i++) {
				nr = n.row + dr[i];
				nc = n.col + dc[i];
				
				if(!isValid(nr, nc) || visited[currKey][nr][nc]) { continue; }
					
				if(isAvailable(nr, nc)) { //1.지나갈 수 있는 길이라면
					visited[currKey][nr][nc] = true;
					queue.add(new Node(nr, nc, width + 1, currKey));
				}
				else if(isKey(nr, nc)) { //2.열쇠가 있는 곳이라면
					int newKey = 1 << (matrix[nr][nc] - 'a');
					newKey = newKey | currKey; //새 열쇠를 기록한다.
					
					if(visited[newKey][nr][nc]) { continue; }
					
					visited[currKey][nr][nc] = true;
					visited[newKey][nr][nc] = true;
					queue.add(new Node(nr, nc, width + 1, newKey));
				}
				else if(isDoor(nr, nc)) { //3.문이 있는 곳이라면
					int door = 1 << (matrix[nr][nc] - 'A');
					
					if((currKey & door) > 0) { //and 연산 : key와 문의 알파벳이 서로 맞다면
						visited[currKey][nr][nc] = true;
						queue.add(new Node(nr, nc, width + 1, currKey));
					}
				}
			}
		}
		
		return -1;
	}

	private static boolean isAvailable(int nr, int nc) { //지나갈 수 있는 길인지 확인
		return matrix[nr][nc] == BLANK || matrix[nr][nc] == '0' || matrix[nr][nc] == '1';
	}

	private static boolean isKey(int nr, int nc) { //현재 밟은 곳이 열쇠인지 확인
		return matrix[nr][nc] >= 'a' && matrix[nr][nc] <= 'z';
	}
	
	private static boolean isDoor(int nr, int nc) { //현재 밟은 곳이 문인지 확인
		return matrix[nr][nc] >= 'A' && matrix[nr][nc] <= 'Z';
	}

	private static boolean isValid(int nr, int nc) {
		return (nr > -1 && nc > -1 && nr < N && nc < M) && (matrix[nr][nc] != WALL);
	}
}

class Node {
	int row;
	int col;
	int width;
	int key;
	
	public Node(int row, int col, int width, int key) {
		this.row = row;
		this.col = col;
		this.width = width;
		this.key = key;
	}
}

---

 

참고한 블로그

https://ghkvud2.tistory.com/13