[백준/자바] 1194 달이 차오른다, 가자.

1194 달이 차오른다, 가자.  사진 클릭시 문제로 이동

---

문제

지금 민식이가 계획한 여행은 달이 맨 처음 뜨기 시작할 때부터, 준비했던 여행길이다.

하지만, 매번 달이 차오를 때마다 민식이는 어쩔 수 없는 현실의 벽 앞에서 다짐을 포기하고 말았다.

민식이는 매번 자신의 다짐을 말하려고 노력했지만, 말을 하면 아무도 못 알아들을 것만 같아서, 지레 겁먹고 벙어리가 되어버렸다.

결국 민식이는 모두 잠든 새벽 네시 반쯤 홀로 일어나, 창 밖에 떠있는 달을 보았다.

하루밖에 남지 않았다. 달은 내일이면 다 차오른다.

이번이 마지막 기회다.

이걸 놓치면 영영 못간다.

영식이는 민식이가 오늘도 여태 것처럼 그냥 잠들어버려서 못 갈지도 모른다고 생각했다.

하지만 그러기엔 민식이의 눈에는 저기 뜬 달이 너무나 떨렸다.

민식이는 지금 미로 속에 있다.

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

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

달이 차오르는 기회를 놓치지 않기 위해서, 미로를 탈출하려고 한다.

한 번의 움직임은 현재 위치에서 수평이나 수직으로 한 칸 이동하는 것이다.

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

입력

첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50)

둘째 줄부터 N개의 줄에 미로의 모양이 주어진다.

같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다.

그리고, 영식이가 열쇠를 숨겨놓는 다면 문에 대응하는 열쇠가 없을 수도 있다.

0은 한 개, 1은 적어도 한 개 있다. 그리고, 열쇠는 여러 번 사용할 수 있다.

출력

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

예제 입력 1

1 7
f0.F..1

예제 출력 1

7

예제 입력 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

55

---

설명

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

이 있다.

소문자를 만나면 열쇠를 집게 되는데 이때 열쇠 집는 것은 비트 마스크 bitmask를 이용해 표현한다.

아스키코드에 따르면 소문자 a는 97이고 b = 98 ,... 1씩 증가한다.

이때 소문자의 값에 - 97을 하면 a = 0, b = 1,...이라는 수를 가지게 되고 이 값을 기준으로 

$$a는 2^{0}자리, 
b는 2^{1}자리, ..$$

다음 식을 통해 원래 key에 해당 자리의 key를 새로 추가한다.

cur.key | (1<<((int)map[x][y]-97))

 

bfs로 자리를 탐색하다가 대문자인 문을 만났을 때 역시 대문자의 아스키코드를 활용한다.

A = 65, B = 67,...로 1씩 증가한다.

대문자 - 65를 수행하면 A = 0, B = 1,...이라는 수를 가지게 되고 이 값을 기준으로

$$A는 2^{0}자리,
B는 2^{1}자리, ...$$

다음 수식을 이용해 0보다 크면 해당 문에 해당하는 키가 존재하고 아니라면 해당 키가 존재하지 않는 것을 판단할 수 있다.

cur.key & (1<<((int)map[x][y]-65))

코드