카테고리 없음
[백준-1194] 달이 차오른다, 가자
또도닝
2021. 4. 17. 14:43
이 문제는 백준의 골드 1레벨 문제이다.
입력은 똑같이 받아주고, map에 0이 나오는 곳이 출발지이기 때문에 출발지가 나오면 move 함수에 넣어주었다.
다른 bfs와 비슷하게 큐에 넣고 큐가 끝나면 끝나는 방식이지만, 까다로운 부분이 있다.
바로 열쇠랑 문을 처리하는 부분이다.
일단 열쇠가 6개나 되고, 그 각각에 맞는 문이 있다.
게다가 문제에서 어떤 열쇠와 어떤 문이 주어질 지 모른다.
그래서 열쇠를 해결하기 위해 비트마스킹을 이용했다.
a부터 f까지 각각 이진수를 이용해 000001 부터, 100000 으로 처리해주고,
a와 b가 있다면 000011, a와 f가 있다면 100001 식으로 처리해서 방문 여부 체킹을 해주었다.
사실 이 부분만 잘 처리하면 다른 bfs와 비슷하게 풀 수 있는 문제인데, 이 부분 처리가 조금 어려웠다.
열쇠를 획득하면 지금 가지고 있는 key 값과 OR(|) 연산을 이용해 추가해주었고,
-> OR 연산은 둘 중 하나만 TRUE 여도 TRUE
문을 발견하면 AND(&) 연산을 이용해 풀어주었다.
-> AND 연산은 둘 다 TRUE여야 TRUE
package ex_0413;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
public class 달이차오른다_1194 {
static int N,M;
static int ans = 10000;
static char[][] map;
static boolean[][][] visited;
static int[] dr = {0,0,-1,1}; //좌우상하
static int[] dc = {-1,1,0,0};
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] s = br.readLine().split(" ");
N = Integer.parseInt(s[0]); //세로
M = Integer.parseInt(s[1]); //가로
map = new char[N][M]; //지도
visited = new boolean[N][M][64]; //a-f까지 총 6개의 열쇠가 있을수도 없을수도 있음.
for(int i=0; i<N; i++) {
s[0] = br.readLine();
for(int j=0; j<M; j++) {
map[i][j] = s[0].charAt(j);
}
}
out: for(int i=0; i<N; i++) {
for(int j=0; j<M; j++) {
if(map[i][j] == '0') { //0은 하나밖에 없으니까 나오면 끝.
move(i,j);
break out;
}
}
}
System.out.println(ans == 10000 ? -1 : ans);
}
static void move(int r, int c) {
Queue<Point> q = new LinkedList<>();
visited[r][c][0] = true;
q.add(new Point(r,c,0,0));
while(!q.isEmpty()) {
Point p = q.poll();
for(int i=0; i<4; i++) {
int nr = p.r+ dr[i];
int nc = p.c + dc[i];
//범위 넘어가면 pass.
if(nr<0 || nc<0 || nr>=N|| nc>=M)
continue;
//출구를 찾으면 끝.
if(map[nr][nc] == '1'){
ans = p.cnt+1;
return;
}
//벽을 만나거나, 방문한 적 있으면 pass
else if(map[nr][nc] == '#' || visited[nr][nc][p.key])
continue;
//그냥 땅이면 들어가기
else if(map[nr][nc] == '.' || map[nr][nc] == '0') {
visited[nr][nc][p.key] = true;
q.add(new Point(nr,nc,p.cnt+1, p.key));
}
//열쇠 찾으면 습득
else if(map[nr][nc] >= 'a' && map[nr][nc] <= 'f') {
int key = 1 << map[nr][nc]-'a';
visited[nr][nc][p.key] = true;
q.add(new Point(nr,nc,p.cnt+1, p.key|key));
}
//문 만났을 때
else if(map[nr][nc] >= 'A' && map[nr][nc] <= 'F') {
int key = 1 << map[nr][nc]-'A';
//key를 가지고 있으면 들어가기
if((p.key&key) == key) {
visited[nr][nc][p.key] = true;
q.add(new Point(nr,nc,p.cnt+1, p.key));
}
}
}
}
}
static class Point{
int r, c, cnt, key;
Point(int r, int c, int cnt, int key){
this.r = r;
this.c = c;
this.cnt = cnt;
this.key = key;
}
}
}