Life Engineering
[BOJ 1194] 달이 차오른다, 가자. (Java) 본문
https://www.acmicpc.net/problem/1194
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main_BOJ_1194 {
static int[] dr= {-1,1,0,0};
static int[] dc= {0,0,-1,1};
static int N, M;
static char[][] map;
static int[][][] check;
static int answer=Integer.MAX_VALUE;
static int start_r, start_c;
static ArrayList<int[]> exits=new ArrayList<>();
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 char[N][M];
check=new int[N][M][64];
for (int i=0; i<N; i++) {
String s=br.readLine();
for (int j = 0; j < M; j++) {
map[i][j]=s.charAt(j);
if (map[i][j]=='0') {
start_r=i;
start_c=j;
}
else if (map[i][j]=='1') {
exits.add(new int[] {i,j});
}
for (int k=0; k<64; k++) {
check[i][j][k]=-1;
}
}
}
bfs();
for (int i=0; i<exits.size(); i++) {
int r=exits.get(i)[0];
int c=exits.get(i)[1];
for (int j=0; j<64; j++) {
if (check[r][c][j]!=-1) {
answer=Math.min(answer, check[r][c][j]);
}
}
}
System.out.println(answer==Integer.MAX_VALUE ? -1: answer);
}
private static void bfs() {
Queue<int[]> q=new LinkedList<>();
q.add(new int[] {start_r, start_c, 0});
check[start_r][start_c][0]=0;
while (!q.isEmpty()) {
int[] curr=q.poll();
int r=curr[0];
int c=curr[1];
int keys=curr[2];
//System.out.println(r+","+c+","+keys);
for (int i=0; i<4; i++) {
int nr=r+dr[i];
int nc=c+dc[i];
if (nr<0 || nc<0 || nr>=N || nc>=M) continue;
if ((map[nr][nc]=='.' || map[nr][nc]=='0') && check[nr][nc][keys]==-1) {
check[nr][nc][keys]=check[r][c][keys]+1;
q.add(new int[] {nr, nc, keys});
}
else if (map[nr][nc]>='a' && map[nr][nc]<='f') {
int b=map[nr][nc]-'a';
int nkeys=keys|(1<<b);
if (check[nr][nc][nkeys]==-1) {
check[nr][nc][nkeys]=check[r][c][keys]+1;
q.add(new int[] {nr, nc, nkeys});
}
}
else if (map[nr][nc]>='A' && map[nr][nc]<='F' && check[nr][nc][keys]==-1) {
int b=map[nr][nc]-'A';
int flag=keys&(1<<b);
if (flag>0) {
check[nr][nc][keys]=check[r][c][keys]+1;
q.add(new int[] {nr, nc, keys});
}
}
else if (map[nr][nc]=='1' && check[nr][nc][keys]==-1) { //도착점 방문 표시
check[nr][nc][keys]=check[r][c][keys]+1;
}
}
}
}
}
비트마스킹+check 3차원 배열을 이용한 BFS 탐색이다.
코드에서 조금 아쉬운 부분은 도착점에 제일 먼저 도착하면 바로 답을 출력해주면 된다는 것이다.
BFS는 (r,c)에 처음 도착할 때가 최소점이므로.
처음에 도착점을 방문했을 때 방문 확인을 안해줘서 최솟값이 아닌 것이 답으로 출력되었다..
그래서 더 깔끔하게 풀려면 큐에서 꺼냈을때, 도착점일때 답을 출력해야 된다.
그리고 이 문제의 포인트는 1. 비트마스킹 2. 3차원 visited 배열인데,
열쇠를 하나 잡을 때마다 비트마스크 해서 그 열쇠를 얻었다는 것을 체크해주고, 그쪽으로 visited 배열을 변경하면서 탐색을 해준다..
다음 코드는 조금 최적화한 코드.. (탐색 시 도착점을 발견하면 바로 그 거리를 리턴하도록! (BFS=>먼저 도착하는 점이 곧 최소거리다!)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main_BOJ_1194 {
static int[] dr= {-1,1,0,0};
static int[] dc= {0,0,-1,1};
static int N, M;
static char[][] map;
static int[][][] check;
static int answer=-1;
static int start_r, start_c;
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 char[N][M];
check=new int[N][M][64];
for (int i=0; i<N; i++) {
String s=br.readLine();
for (int j = 0; j < M; j++) {
map[i][j]=s.charAt(j);
if (map[i][j]=='0') {
start_r=i;
start_c=j;
}
for (int k=0; k<64; k++) {
check[i][j][k]=-1;
}
}
}
bfs();
System.out.println(answer);
}
private static void bfs() {
Queue<int[]> q=new LinkedList<>();
q.add(new int[] {start_r, start_c, 0});
check[start_r][start_c][0]=0;
while (!q.isEmpty()) {
int[] curr=q.poll();
int r=curr[0];
int c=curr[1];
int keys=curr[2];
//System.out.println(r+","+c+","+keys);
if (map[r][c]=='1') {
answer=check[r][c][keys];
return;
}
for (int i=0; i<4; i++) {
int nr=r+dr[i];
int nc=c+dc[i];
if (nr<0 || nc<0 || nr>=N || nc>=M) continue;
if ((map[nr][nc]=='.' || map[nr][nc]=='0' || map[nr][nc]=='1') && check[nr][nc][keys]==-1) {
check[nr][nc][keys]=check[r][c][keys]+1;
q.add(new int[] {nr, nc, keys});
}
else if (map[nr][nc]>='a' && map[nr][nc]<='f') {
int b=map[nr][nc]-'a';
int nkeys=keys|(1<<b);
if (check[nr][nc][nkeys]==-1) {
check[nr][nc][nkeys]=check[r][c][keys]+1;
q.add(new int[] {nr, nc, nkeys});
}
}
else if (map[nr][nc]>='A' && map[nr][nc]<='F' && check[nr][nc][keys]==-1) {
int b=map[nr][nc]-'A';
int flag=keys&(1<<b);
if (flag>0) {
check[nr][nc][keys]=check[r][c][keys]+1;
q.add(new int[] {nr, nc, keys});
}
}
}
}
}
}
'Problem Solving' 카테고리의 다른 글
[BOJ 14442] 벽 부수고 이동하기 2 (Java) (0) | 2022.04.03 |
---|---|
[BOJ 20057] 마법사 상어와 토네이도 (Java) (0) | 2022.04.01 |
[BOJ 4485] 녹색 옷 입은 애가 젤다지? (Java) (0) | 2022.04.01 |
[BOJ 1062] 가르침 (Java) (0) | 2022.03.31 |
[BOJ 1600] 말이 되고픈 원숭이 (Java) (0) | 2022.03.30 |