[Java] 백준 1194번 : 달이 차오른다, 가자.

코딩테스트/그래프 탐색

[Java] 백준 1194번 : 달이 차오른다, 가자.

sujin7837 2022. 4. 1. 13:51

문제

지금 민식이가 계획한 여행은 달이 맨 처음 뜨기 시작할 때 부터, 준비했던 여행길이다. 하지만, 매번 달이 차오를 때마다 민식이는 어쩔 수 없는 현실의 벽 앞에서 다짐을 포기하고 말았다.

민식이는 매번 자신의 다짐을 말하려고 노력했지만, 말을 하면 아무도 못 알아들을 것만 같아서, 지레 겁먹고 벙어리가 되어버렸다. 결국 민식이는 모두 잠든 새벽 네시 반쯤 홀로 일어나, 창 밖에 떠있는 달을 보았다.

하루밖에 남지 않았다. 달은 내일이면 다 차오른다. 이번이 마지막기회다. 이걸 놓치면 영영 못간다.

영식이는 민식이가 오늘도 여태것처럼 그냥 잠 들어버려서 못 갈지도 모른다고 생각했다. 하지만 그러기엔 민식이의 눈에는 저기 뜬 달이 너무나 떨렸다.

민식이는 지금 미로 속에 있다. 미로는 직사각형 모양이고, 여행길을 떠나기 위해 미로를 탈출하려고 한다. 미로는 다음과 같이 구성되어져있다.

빈 칸: 언제나 이동할 수 있다. ('.')
벽: 절대 이동할 수 없다. ('#')
열쇠: 언제나 이동할 수 있다. 이 곳에 처음 들어가면 열쇠를 집는다. ('a', 'b', 'c', 'd', 'e', 'f')
문: 대응하는 열쇠가 있을 때만 이동할 수 있다. ('A', 'B', 'C', 'D', 'E', 'F')
민식이의 현재 위치: 빈 곳이고, 민식이가 현재 서 있는 곳이다. ('0')
출구: 달이 차오르기 때문에, 민식이가 가야하는 곳이다. 이 곳에 오면 미로를 탈출한다. ('1')

달이 차오르는 기회를 놓치지 않기 위해서, 미로를 탈출하려고 한다. 한 번의 움직임은 현재 위치에서 수평이나 수직으로 한 칸 이동하는 것이다.

민식이가 미로를 탈출하는데 걸리는 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, 문에 대응하는 열쇠가 없을 수도 있다. '0'은 한 개, '1'은 적어도 한 개 있다. 열쇠는 여러 번 사용할 수 있다.

출력

첫째 줄에 민식이가 미로를 탈출하는데 드는 이동 횟수의 최솟값을 출력한다. 만약 민식이가 미로를 탈출 할 수 없으면, -1을 출력한다.

예제 입력 1

1 7
f0.F..1

예제 출력 1

예제 입력 2

5 5
....1
#1###
.1.#0
....A
.1.#.

예제 출력 2

-1

예제 입력 3

7 8
a#c#eF.1
.#.#.#..
.#B#D###
0....F.1
C#E#A###
.#.#.#..
d#f#bF.1

예제 출력 3

예제 입력 4

3 4
1..0
###.
1...

예제 출력 4

예제 입력 5

3 5
..0..
.###.
..1.A

예제 출력 5

예제 입력 6

4 5
0....
.#B#A
.#.#.
b#a#1

예제 출력 6

예제 입력 7

1 11
c.0.C.C.C.1

예제 출력 7

예제 입력 8

3 6
###...
#0A.1a
###...

예제 출력 8

-1

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	private static BufferedReader bf;
	private static StringTokenizer st;

	private static int N, M, R, C;
	private static char[][] maze;
	private static int[][] dist;
	private static int[] dx = { -1, 1, 0, 0 };
	private static int[] dy = { 0, 0, -1, 1 };

	static class Minsik {
		int r, c, cnt, key;	// cnt : 이동 횟수, key : 획득한 key의 종류 비트로 저장

		public Minsik(int r, int c, int cnt, int key) {
			super();
			this.r = r;
			this.c = c;
			this.cnt = cnt;
			this.key = key;
		}

		@Override
		public String toString() {
			return "Minsik [r=" + r + ", c=" + c + ", cnt=" + cnt + ", key=" + key + "]";
		}

	}

	public static void main(String[] args) throws IOException {

		bf = new BufferedReader(new InputStreamReader(System.in));
		st = new StringTokenizer(bf.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		maze = new char[N][M];
		dist = new int[N][M];
		for (int i = 0; i < N; i++)
			Arrays.fill(dist[i], Integer.MAX_VALUE);

		for (int r = 0; r < N; r++) {
			String s = bf.readLine();
			for (int c = 0; c < M; c++) {
				maze[r][c] = s.charAt(c);
				if (maze[r][c] == '0') {
					R = r;
					C = c;
					dist[r][c] = 0;
					maze[r][c] = '.';
				}
			}
		}
		move(R, C);
	}

	public static void move(int r, int c) {
		Queue<Minsik> queue = new LinkedList<>();
		queue.add(new Minsik(r, c, 0, 0));

		boolean [][][]visited=new boolean[N][M][(int) Math.pow(2,6)];	// 열쇠가 총 6개이므로 이를 비트마스킹으로 나타내주기 위해 2^6만큼의 공간을 만들어줌
		visited[r][c][0]=true;
		
		while(!queue.isEmpty()) {
			Minsik minsik=queue.poll();
			int R=minsik.r;
			int C=minsik.c;
			int cnt=minsik.cnt;
			int key=minsik.key;
			
			for(int i=0;i<4;i++) {
				int nx=R+dx[i];
				int ny=C+dy[i];
				
				if(isIn(nx, ny) && !visited[nx][ny][key]) {
					if(maze[nx][ny]=='1') {	// 출구
						System.out.println(cnt+1);
						return;
					} else if(maze[nx][ny]=='#') continue;	// 벽
					else if(maze[nx][ny]=='.') {	// 빈 칸
						visited[nx][ny][key]=true;
						queue.add(new Minsik(nx, ny, cnt+1, key));
					} else if(isKey(nx, ny)) {	// 열쇠
						int newKey=1<<(maze[nx][ny]-'a');
						newKey|=key;	// 새로 획득한 열쇠 추가
						if(!visited[nx][ny][newKey]) {
							visited[nx][ny][key]=true;
							visited[nx][ny][newKey]=true;
							queue.add(new Minsik(nx, ny, cnt+1, newKey));
						}
					} else if(isDoor(nx, ny)) {	// 문
						boolean check=((key & (1<<(maze[nx][ny]-'A')))!=0);
						if(check) {	// 열쇠를 갖고있는 경우
							visited[nx][ny][key]=true;
							queue.add(new Minsik(nx, ny, cnt+1, key));
						} else continue;	// 열쇠가 없는 경우
					}
				}
			}
		}
		System.out.println(-1);
		return;
	}

	public static boolean isKey(int r, int c) {
		return maze[r][c] >= 'a' && maze[r][c] <= 'f';
	}

	public static boolean isDoor(int r, int c) {
		return maze[r][c] >= 'A' && maze[r][c] <= 'F';
	}

	public static boolean isIn(int r, int c) {
		return r >= 0 && r < N && c >= 0 && c < M;
	}
}

bfs와 비트마스킹을 함께 사용해야해서 어려웠던 문제입니다.

열쇠를 획득하는 과정에서 비트마스킹을 사용해주었고, 열쇠 획득 여부에 따라 경로의 방문 여부를 체크해주어야 하기 때문에 visited 배열을 3차원으로 만들어주었습니다.

가지고 있는 열쇠를 비트마스킹으로 설정해줄 때 아래와 같은 방법을 사용했습니다.

a : 000001

b : 000010

c : 000100

d : 001000

e : 010000

f : 100000

열쇠를 획득하게 되면 key = 현재 열쇠 | 획득한 열쇠 를 통해 key 값을 업데이트하고, 문을 마주하여 가지고 있는 열쇠 여부를 확인할 때는 key & door 값이 0이면 열쇠가 없고, 0보다 크면 열쇠가 있다고 판단하였습니다.

출처 : https://ghkvud2.tistory.com/13

'코딩테스트 > 그래프 탐색' 카테고리의 다른 글

[Java] 백준 13460번 : 구슬 탈출2 (0)	2022.04.01
[Java] 백준 13459번 : 구슬 탈출 (0)	2022.04.01
[Java] 백준 1261번 : 알고스팟 (0)	2022.03.31
[Java] 백준 1865번 : 웜홀 (0)	2022.03.30
[Java] 백준 2206번 : 벽 부수고 이동하기 (0)	2022.03.30

현재글[Java] 백준 1194번 : 달이 차오른다, 가자.

sujin's 개발 로그