[BOJ 1194] 달이 차오른다, 가자. (Java)

https://www.acmicpc.net/problem/1194

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});
					}
				}
			}
		}
		
	}
}