OJ
[BOJ] 1194 달이 차오른다, 가자. (JAVA)
P3PP4
2022. 10. 7. 23:00
https://www.acmicpc.net/problem/1194
1194번: 달이 차오른다, 가자.
첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고,
www.acmicpc.net
골드 1 문제입니다.
BFS를 사용하며 열쇠를 주우면 열쇠 정보를 들고 다녀야 합니다.
가지고 있는 열쇠가 무엇인지는 비트 마스킹으로 해결했습니다.
visited = new int[1 << 6][N][M];6개의 열쇠까지 가지고 다닐 수 있기 때문에 visited 배열은 3차원이고, 1을 6번 시프트한 크기만큼이 필요합니다.
열쇠를 6개 모두 모으면 111_111(2)이 되기 때문에 1_000_000(2)의 크기만큼 선언합니다.
case 'a':
case 'b':
case 'c':
case 'd':
case 'e':
case 'f':
newKey |= (1 << (temp - 97));
visited[newKey][nr][nc] = visited[now.key][now.row][now.col] + 1;
visited[now.key][nr][nc] = visited[now.key][now.row][now.col] + 1;
q.offer(new Pos(nr, nc, newKey));
break;현재 가지고 있는 열쇠가 000_010(2)일 때(열쇠 b만 가지고 있을 때), 만약 열쇠 e를 줍는다면
newKey는 000_010(2) | 010_000(2) = 010_010(2)이 됩니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int N, M;
static char[][] map;
static int[][][] visited;
static Queue<Pos> q = new LinkedList<Pos>();
static int[] dr = { -1, 0, 1, 0 };
static int[] dc = { 0, 1, 0, -1 };
public static void main(String[] args) throws IOException {
st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new char[N][M];
visited = new int[1 << 6][N][M];
for (int i = 0; i < N; i++) {
String str = br.readLine();
for (int j = 0; j < M; j++) {
map[i][j] = str.charAt(j);
if(map[i][j] == '0') {
q.offer(new Pos(i, j, 0));
visited[0][i][j] = 1;
}
}
} // 입력 끝
while(!q.isEmpty()) {
Pos now = q.poll();
for (int dir = 0; dir < 4; dir++) {
int nr = now.row + dr[dir];
int nc = now.col + dc[dir];
if(0 <= nr && nr < N && 0 <= nc && nc < M && visited[now.key][nr][nc] == 0 && map[nr][nc] != '#') {
char temp = map[nr][nc];
int newKey = now.key;
switch (temp) {
case '1':
System.out.println(visited[now.key][now.row][now.col]);
return;
case '.':
case '0':
visited[now.key][nr][nc] = visited[now.key][now.row][now.col] + 1;
q.offer(new Pos(nr, nc, now.key));
break;
case 'a':
case 'b':
case 'c':
case 'd':
case 'e':
case 'f':
newKey |= (1 << (temp - 97));
visited[newKey][nr][nc] = visited[now.key][now.row][now.col] + 1;
visited[now.key][nr][nc] = visited[now.key][now.row][now.col] + 1;
q.offer(new Pos(nr, nc, newKey));
break;
case 'A':
case 'B':
case 'C':
case 'D':
case 'E':
case 'F':
if((now.key & (1 << (temp - 65))) != 0) {
visited[now.key][nr][nc] = visited[now.key][now.row][now.col] + 1;
q.offer(new Pos(nr, nc, now.key));
}
break;
}
}
}
}
System.out.println(-1);
}
static class Pos {
int row, col, key;
public Pos(int row, int col, int key) {
this.row = row;
this.col = col;
this.key = key;
}
}
}