BOJ_1194_달이 차오른다, 가자 (Java)
[Gold I] 달이 차오른다, 가자. - 1194
성능 요약
메모리: 16388 KB, 시간: 128 ms
분류
너비 우선 탐색, 비트마스킹, 그래프 이론, 그래프 탐색
제출 일자
2024년 11월 21일 11:05:29
문제 설명
지금 민식이가 계획한 여행은 달이 맨 처음 뜨기 시작할 때 부터, 준비했던 여행길이다. 하지만, 매번 달이 차오를 때마다 민식이는 어쩔 수 없는 현실의 벽 앞에서 다짐을 포기하고 말았다.
민식이는 매번 자신의 다짐을 말하려고 노력했지만, 말을 하면 아무도 못 알아들을 것만 같아서, 지레 겁먹고 벙어리가 되어버렸다. 결국 민식이는 모두 잠든 새벽 네시 반쯤 홀로 일어나, 창 밖에 떠있는 달을 보았다.
하루밖에 남지 않았다. 달은 내일이면 다 차오른다. 이번이 마지막기회다. 이걸 놓치면 영영 못간다.
영식이는 민식이가 오늘도 여태것처럼 그냥 잠 들어버려서 못 갈지도 모른다고 생각했다. 하지만 그러기엔 민식이의 눈에는 저기 뜬 달이 너무나 떨렸다.
민식이는 지금 미로 속에 있다. 미로는 직사각형 모양이고, 여행길을 떠나기 위해 미로를 탈출하려고 한다. 미로는 다음과 같이 구성되어져있다.
- 빈 칸: 언제나 이동할 수 있다. ('.')
- 벽: 절대 이동할 수 없다. ('#')
- 열쇠: 언제나 이동할 수 있다. 이 곳에 처음 들어가면 열쇠를 집는다. ('a', 'b', 'c', 'd', 'e', 'f')
- 문: 대응하는 열쇠가 있을 때만 이동할 수 있다. ('A', 'B', 'C', 'D', 'E', 'F')
- 민식이의 현재 위치: 빈 곳이고, 민식이가 현재 서 있는 곳이다. ('0')
- 출구: 달이 차오르기 때문에, 민식이가 가야하는 곳이다. 이 곳에 오면 미로를 탈출한다. ('1')
달이 차오르는 기회를 놓치지 않기 위해서, 미로를 탈출하려고 한다. 한 번의 움직임은 현재 위치에서 수평이나 수직으로 한 칸 이동하는 것이다.
민식이가 미로를 탈출하는데 걸리는 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, 문에 대응하는 열쇠가 없을 수도 있다. '0'은 한 개, '1'은 적어도 한 개 있다. 열쇠는 여러 번 사용할 수 있다.
출력
첫째 줄에 민식이가 미로를 탈출하는데 드는 이동 횟수의 최솟값을 출력한다. 만약 민식이가 미로를 탈출 할 수 없으면, -1을 출력한다.
문제 풀이
간단한 bfs 구현 문제다. 이렇게 방문처리에 조건이 있는경우 3차원으로 visited 배열을 만들면 된다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
/**
* Author: nowalex322, Kim HyeonJae
*/
import java.io.*;
import java.util.*;
public class Main {
class Person{
int r, c, key, cnt;
Person(int r, int c, int key, int cnt) {
this.r = r;
this.c = c;
this.key = key;
this.cnt = cnt;
}
}
static BufferedReader br;
static BufferedWriter bw;
static StringTokenizer st;
static int N, M, res;
static char board[][];
static boolean visited[][][];
static int[] dr = {0, -1, 0, 1}, dc = {-1, 0, 1, 0};
public static void main(String[] args) throws Exception {
new Main().solution();
}
public void solution() throws Exception {
br = new BufferedReader(new InputStreamReader(System.in));
// br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
bw = new BufferedWriter(new OutputStreamWriter(System.out));
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
board = new char[N+2][M+2];
visited = new boolean[N+2][M+2][1<<(6)];
boolean flag = false; // 0이 있는지 체크
for(int i=0; i<N+2; i++) {
for(int j=0; j<M+2; j++) {
board[i][j] = '#';
}
}
Person p = new Person(1, 1, 0, 0);
for(int i=1; i<=N; i++) {
String s = br.readLine();
for(int j=1; j<=M; j++) {
board[i][j] = s.charAt(j-1);
if (board[i][j] == '0') {
p.r = i;
p.c = j;
flag = true;
}
}
}
if(!flag) {
System.out.println(-1);
return;
}
res = 0;
bfs(p);
bw.write(String.valueOf(res));
bw.flush();
bw.close();
br.close();
}
private void bfs(Person p) {
Queue<Person> queue = new LinkedList<>();
Person start = p;
visited[start.r][start.c][start.key] = true;
queue.offer(start);
while(!queue.isEmpty()) {
Person curr = queue.poll();
for(int k=0; k<4; k++) {
int nr = curr.r + dr[k];
int nc = curr.c + dc[k];
char square = board[nr][nc];
if(visited[nr][nc][curr.key]) continue;
if(square == '#') continue;
Person next = new Person (nr, nc, curr.key, curr.cnt);
if(square == '.' || square == '0') {
next.cnt++;
visited[nr][nc][next.key] = true;
queue.offer(next);
} else if(square >= 'a' && square <= 'f') {
next.key |= 1 << (square - 'a');
next.cnt++;
visited[nr][nc][next.key] = true;
queue.offer(next);
} else if(square >= 'A' && square <= 'F') {
if((next.key & 1 << (square - 'A')) != 0) {
next.cnt++;
visited[nr][nc][next.key] = true;
queue.offer(next);
}
} else if(square == '1') {
res = next.cnt + 1;
return;
}
}
}
res = -1;
}
}