[백준BOJ] 1194번 달이 차오른다 가자.java

 

백준 저지에서 달이 차오른다, 가자를 자바를 통해 풀어 보았다. 

 

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

1194번: 달이 차오른다, 가자.

1194번 달이 차오른다 가자.java

GitHub - tomy9729/Algorithm: 🐗 내가 직접 작성한 내 코드 🐗

 

1194번 달이 차오른다, 가자.

문제

지금 민식이가 계획한 여행은 달이 맨 처음 뜨기 시작할 때 부터, 준비했던 여행길이다. 하지만, 매번 달이 차오를 때마다 민식이는 어쩔 수 없는 현실의 벽 앞에서 다짐을 포기하고 말았다.
민식이는 매번 자신의 다짐을 말하려고 노력했지만, 말을 하면 아무도 못 알아들을 것만 같아서, 지레 겁먹고 벙어리가 되어버렸다. 결국 민식이는 모두 잠든 새벽 네시 반쯤 홀로 일어나, 창 밖에 떠있는 달을 보았다.
하루밖에 남지 않았다. 달은 내일이면 다 차오른다. 이번이 마지막기회다. 이걸 놓치면 영영 못간다.
영식이는 민식이가 오늘도 여태것처럼 그냥 잠 들어버려서 못 갈지도 모른다고 생각했다. 하지만 그러기엔 민식이의 눈에는 저기 뜬 달이 너무나 떨렸다.
민식이는 지금 미로 속에 있다. 미로는 직사각형 모양이고, 여행길을 떠나기 위해 미로를 탈출하려고 한다. 미로는 다음과 같이 구성되어져있다.

- 빈 곳 : 언제나 이동할 수 있다. ('.‘로 표시됨)
- 벽 : 절대 이동할 수 없다. (‘#’)
- 열쇠 : 언제나 이동할 수 있다. 이 곳에 처음 들어가면 열쇠를 집는다. (a - f)
- 문 : 대응하는 열쇠가 있을 때만 이동할 수 있다. (A - F)민식이의 현재 위치 : 빈 곳이고, 민식이가 현재 서 있는 곳이다. (숫자 0)
- 출구 : 달이 차오르기 때문에, 민식이가 가야하는 곳이다. 이 곳에 오면 미로를 탈출한다. (숫자 1)

달이 차오르는 기회를 놓치지 않기 위해서, 미로를 탈출하려고 한다. 한 번의 움직임은 현재 위치에서 수평이나 수직으로 한 칸 이동하는 것이다.
민식이가 미로를 탈출하는데 걸리는 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오.

설명

bfs에 비트마스킹을 사용하지 않으면 메모리 초과 지옥에 걸리는 문제인데 문제를 풀 때 비트마스킹에 대한 개념이 재데로 잡혀있지 않아서 다른 방법으로 풀다가 시간을 많이 썼다.

 

기본적으로 bfs를 통해 미로를 이동한다. 빈 곳이나 열쇠가 있는 곳으로 이동하며 열쇠가 있으면 열쇠를 획득하고 문이 있으면 열쇠가 있는지 확인하고 있다면 문을 지나갈 수 있다. 

 

여기서 고려해야할 것은 bfs를 통해 퍼져나가는 이동에 대해서 열쇠가 있는 경우와 없는 경우를 어떻게 분리할 것이며 방문한 곳을 재방문하는 과정에서 무한루프에 빠지지 않게 할 것인가 이다. 

 

어떤 위치에 대해서 민식이가 위치에 접근할 때 달라지는 것은 민식이가 어떤 열쇠를 가지고 있냐이다. 열쇠의 개수가 6개이므로 가로x세로x6 크기의 배열을 사용하면 어떤 열쇠들을 가지고 있을 때 해당 위치에 방문했는지를 구분지을 수 있다. 단 배열을 각 열쇠들을 정확하게 구분지을 수 있어야 하기 때문에 비트마스킹을 사용한다. 비트마스킹을 통해 열쇠 소지 여부를 구분하고 메모리 사용을 줄일 수 있다.

코드

//1194번 달이 차오른다 가자.java
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 달이_차오른다_가자_1194 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int answer = -1;
	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		char[][] maze = new char[N][M];
		point start = new point(0,0,0,0);
		
		for(int i=0;i<N;i++) {
			String line = br.readLine();
			for(int j=0;j<M;j++) {
				maze[i][j]=line.charAt(j);
				if(maze[i][j]=='0') {
					start = new point(i,j,0,0);
					maze[i][j]='.';
				}
			}
		}
		
		boolean[][][] visit = new boolean[N][M][64];
		bfs(start, visit, maze, N, M);
		System.out.println(answer);
	}
	
	static void bfs(point start, boolean[][][] visit, char[][] maze, int N, int M) {
		int[] di= {0,0,1,-1};
		int[] dj = {1,-1,0,0};
		Queue<point> q = new LinkedList<point>();
		q.add(start);
		
		while(!q.isEmpty()) {
			point now = q.poll();
			for(int d=0;d<4;d++) {
				int nextI = now.i+di[d];
				int nextJ = now.j+dj[d];
				
				if(0>nextI || nextI>=N || 0>nextJ || nextJ>=M)continue;//범위 벗어나면
				if(maze[nextI][nextJ]=='#')continue;//벽이면 
				if(visit[nextI][nextJ][now.key])continue;//이미 방문했으면
				
				//빈곳인 경우
				if(maze[nextI][nextJ]=='.') {
					visit[nextI][nextJ][now.key] = true;
					q.add(new point(nextI,nextJ,now.key,now.dis+1));
				}
				//열쇠가 있는 경우
				else if(0<=maze[nextI][nextJ]-'a' && maze[nextI][nextJ]-'a'<=7) {
					int nextKey = (1<<(maze[nextI][nextJ]-'a')) | now.key;
					if(!visit[nextI][nextJ][nextKey]) {
						visit[nextI][nextJ][nextKey] = true;
						q.add(new point(nextI,nextJ,nextKey,now.dis+1));
					}
				}
				//문이 있는 경우
				else if(0<=maze[nextI][nextJ]-'A' && maze[nextI][nextJ]-'A'<=7) {
					if(((1<<(maze[nextI][nextJ]-'A'))&now.key)>0) {
						visit[nextI][nextJ][now.key] = true;
						q.add(new point(nextI,nextJ,now.key,now.dis+1));
					}
				}
				//도착
				else if(maze[nextI][nextJ]=='1') {
					answer = now.dis+1;
					return;
				}
			}
		}
	}
	
	static class point{
		int i;
		int j;
		int key;
		int dis;
		point(int i, int j,int key, int dis){
			this.i=i;
			this.j=j;
			this.key=key;
			this.dis=dis;
		}
	}
}