[백준] 1194. 달이 차오른다, 가자. (JAVA)

🌖 달이 차오른다, 가자.

 

여전히 그래프 탐색은 어려웡

 

---

문제

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

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

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

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

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

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

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

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

 

입력

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

 

출력

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

 

---

🔑 IDEA

• 열쇠는 한번 주우면 계속 쓸 수 있다. 👉 비트마스킹으로 열쇠 정보를 나타낸다.
• 열쇠를 얻은 뒤 왔던 길을 되돌아 갈 수 있다. 👉 visited 정보를 row, col, key 로 체크한다. 

 

💡  나의 풀이

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

class Node {
	int r;
	int c;
	int key;
	int cnt;

	Node(int r, int c, int key, int cnt) {
		this.r = r;
		this.c = c;
		this.key = key;
		this.cnt = cnt;
	}
}

class Main {
	static int R;
	static int C;
	static Node start;
	static char[][] map;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		map = new char[R][C];

		for(int r=0; r<R; r++) {
			map[r] = br.readLine().toCharArray();
			for(int c=0; c<C; c++) {
				if(map[r][c] == '0')
					start = new Node(r,c,0, 0);
			}
		}
		System.out.println(bfs());
	}

	private static int bfs() {
		int[] rMove = new int[]{-1,1,0,0};
		int[] cMove = new int[]{0,0,-1,1};
		Queue<Node> queue = new LinkedList<>();
		boolean[][][] visited = new boolean[R][C][1<<6];

		queue.offer(start);
		visited[start.r][start.c][0] = true;

		while(!queue.isEmpty()) {
			Node cur = queue.poll();
			int key = cur.key;
			int cnt = cur.cnt;

			if(map[cur.r][cur.c] == '1')
				return cnt;

			for(int i=0; i<4; i++) {
				int nr = cur.r + rMove[i];
				int nc = cur.c + cMove[i];

				if(nr<0 || nc<0 || nr>=R || nc>=C) continue;
				if(visited[nr][nc][key] || map[nr][nc] == '#') continue;

				if('a' <= map[nr][nc] && map[nr][nc] <= 'f') {
					int nk = key | (1 << (map[nr][nc]-'a'));
					if(visited[nr][nc][nk]) continue;
					visited[nr][nc][key] = true;
					visited[nr][nc][nk] = true;
					queue.offer(new Node(nr,nc,nk,cnt+1));
				}

				else if('A' <= map[nr][nc] && map[nr][nc] <= 'F') {
					if((key & (1 << (map[nr][nc] - 'A'))) == 0) continue;
					visited[nr][nc][key] = true;
					queue.offer(new Node(nr,nc,key,cnt+1));
				}

				else {
					visited[nr][nc][key] = true;
					queue.offer(new Node(nr,nc,key,cnt+1));
				}
			}
		}
		return -1;
	}
}

 

 

---

 

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