#1194 달이 차오른다, 가자
난이도 : 골드 1
유형 : BFS / 비트마스크
▸ 문제
지금 민식이가 계획한 여행은 달이 맨 처음 뜨기 시작할 때 부터, 준비했던 여행길이다. 하지만, 매번 달이 차오를 때마다 민식이는 어쩔 수 없는 현실의 벽 앞에서 다짐을 포기하고 말았다.
민식이는 매번 자신의 다짐을 말하려고 노력했지만, 말을 하면 아무도 못 알아들을 것만 같아서, 지레 겁먹고 벙어리가 되어버렸다. 결국 민식이는 모두 잠든 새벽 네시 반쯤 홀로 일어나, 창 밖에 떠있는 달을 보았다.
하루밖에 남지 않았다. 달은 내일이면 다 차오른다. 이번이 마지막기회다. 이걸 놓치면 영영 못간다.
영식이는 민식이가 오늘도 여태것처럼 그냥 잠 들어버려서 못 갈지도 모른다고 생각했다. 하지만 그러기엔 민식이의 눈에는 저기 뜬 달이 너무나 떨렸다.
민식이는 지금 미로 속에 있다. 미로는 직사각형 모양이고, 여행길을 떠나기 위해 미로를 탈출하려고 한다. 미로는 다음과 같이 구성되어져있다.
- 빈 곳 : 언제나 이동할 수 있다. ('.‘로 표시됨)
- 벽 : 절대 이동할 수 없다. (‘#’)
- 열쇠 : 언제나 이동할 수 있다. 이 곳에 처음 들어가면 열쇠를 집는다. (a - f)
- 문 : 대응하는 열쇠가 있을 때만 이동할 수 있다. (A - F)
- 민식이의 현재 위치 : 빈 곳이고, 민식이가 현재 서 있는 곳이다. (숫자 0)
- 출구 : 달이 차오르기 때문에, 민식이가 가야하는 곳이다. 이 곳에 오면 미로를 탈출한다. (숫자 1)
달이 차오르는 기회를 놓치지 않기 위해서, 미로를 탈출하려고 한다. 한 번의 움직임은 현재 위치에서 수평이나 수직으로 한 칸 이동하는 것이다.
민식이가 미로를 탈출하는데 걸리는 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오.
▸ 입력
첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, 영식이가 열쇠를 숨겨놓는 다면 문에 대응하는 열쇠가 없을 수도 있다. 0은 한 개, 1은 적어도 한 개 있다. 그리고, 열쇠는 여러 번 사용할 수 있다.
▸ 출력
첫째 줄에 민식이가 미로를 탈출하는데 드는 이동 횟수의 최솟값을 출력한다. 만약 민식이가 미로를 탈출 할 수 없으면, -1을 출력한다.
문제 풀이
BFS + 비트마스크
제목이 이상해서 다른 문제를 풀려고하다가 2021 카카오 인턴 코테 4번 문제와 유형이 비슷하여 풀이를 하였다.
카카오 문제는 우선순위 큐를 활용한 다익스트라 + 비트마스크의 유형이었다면 해당 문제는 그와 비슷한 BFS + 비트마스크 문제이다.
* BFS와 다익스트라의 차이는 그래프에 가중치가 있고 없고의 차이라고 보면 된다.
해당 문제는 단순 BFS문제에서 key와 door라는 장치만 추가되었다고 볼 수 있다.
Key, Door
총 6가지의 key와 door는 각 쌍을 이룬다. 영식이는 그래프를 움직일 때 마다 키를 지니고있는지 없는지 상태 여부를 체크해줘야 한다. 그래야 문을 만났을 때 해당 문을 통과할 수 있는지 없는지 판단할 수 있기 때문이다.
key의 상태 표현은 비트마스킹을 활용해 줄 것이다. 비트마스킹은 메모리 사용도 줄이고 간결하게 코딩을 할 수 있다는 장점을 가지고 있다,
// 배열
boolean[] keyStatus = {1,1,0,0, ...};
// 비트마스킹
int keyStatus = 1100...;
구상
영식이가 길을 걷다가 마주할 상황은 총 4가지이다.
- '#' 벽을 만난다
- '.' 그냥 길을 걷는다.
- 'a'~'f' key를 줍는다.
- 'A'~'F' 문을 마주한다.
1,2번 케이스
1,2번은 그냥 BFS탐색과 똑같이 '#' 벽을 만나면 경로 탐색은 종료하고, '.' 을 만나면 계속해서 탐색을 진행한다.
3번 케이스
'a'~'f'에 맞는 key의 상태를 업데이트해준다.
int nextStatus = key|status; // key 상태 업데이트
4번 케이스
4번 현재 영식이가 지닌 key의 상태를 확인하여 해당 문을 열 수 있는지 확인한다.
if(status & key = key){
// true이면 문을 열 수 있으므로 탐색진행
// false이면 해당 문을 열 수 없으므로 탐색 종료
}
그리고 '1'을 만나면 탐색을 종료해주면 된다. '1'은 맵에 1개 이상 존재하므로 좌표로 특정지어서는 안된다.
풀이 코드
import java.io.*;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int n,m;
static int[][] map;
static Map<Integer, Integer> key;
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
static int answer = -1;
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());
map = new int[n][m];
key = new HashMap<>();
int start_x=0, start_y=0;
for(int i=0; i<n; i++) {
String line = br.readLine();
// '#': 0, '.': 11, '0':13, '1':14,
// 'a' 62 ~ 'f' 67
// 'A' 30 ~ 'F' 35
for(int j=0; j<m; j++) {
int num = line.charAt(j)-35;
if(num == 13) {
start_x = j;
start_y = i;
}
else if(num>61 && num <68) { // key 저장
if(!key.containsKey(num)) {
key.put(num, 1<<(num-61));
}
}
map[i][j] = num;
}
}
bfs(start_x, start_y);
System.out.println(answer);
}
static void bfs(int x, int y) {
Queue<int[]> q = new LinkedList<>();
boolean[][][] visited = new boolean[n][m][1<<7];
q.add(new int[] {x,y,0,0});
visited[y][x][0] = true;
while(!q.isEmpty()) {
int[] pos = q.poll();
int px = pos[0];
int py = pos[1];
int status = pos[2];
int move = pos[3];
if(map[py][px] == 14) {
answer = move;
return;
}
for(int i=0; i<4; i++) {
int nx = px + dx[i];
int ny = py + dy[i];
if(nx <0 || ny<0 || nx>m-1 || ny>n-1 ) continue;
if(map[ny][nx] == 0 || visited[ny][nx][status]) continue;
int nStatus = status;
// key 획득
if(map[ny][nx]>61 && map[ny][nx] <68) {
nStatus = status|key.get(map[ny][nx]); // Key 상태 업데이트
if(!visited[ny][nx][nStatus]) {
visited[ny][nx][nStatus] = true;
q.add(new int[] {nx,ny,nStatus, move+1});
}
}
// door 마주침
else if(map[ny][nx]>29 &&map[ny][nx] <36) {
if(!key.containsKey(map[ny][nx]+32)) continue; // key가 맵에 존재하지 않으면 pass
// 현재 지닌 key와 문 일치하면 탐색 진행
if((status & key.get(map[ny][nx]+32)) == key.get(map[ny][nx]+32)) {
visited[ny][nx][nStatus] = true;
q.add(new int[] {nx,ny,nStatus, move+1});
}
}
// 그냥 길
else {
visited[ny][nx][nStatus] = true;
q.add(new int[] {nx,ny,nStatus,move+1});
}
}
}
}
}
'Dot Algo∙ DS > PS' 카테고리의 다른 글
[BOJ] 백준 2263번 트리의 순회 (Java) (2) | 2021.07.25 |
---|---|
[BOJ] 백준 1991번 트리 순회 (Java) (0) | 2021.07.25 |
[BOJ] 백준 1062번 가르침 (Java) (0) | 2021.07.25 |
[프로그래머스] 2021 카카오 인턴 #5 시험장 나누기 (Java) (0) | 2021.07.25 |
[프로그래머스] 2021 카카오 인턴 #4 미로 탈출 (Java) (0) | 2021.07.21 |