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

제목

출처 : www.acmicpc.net/problem/1194

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

민식이는 달이 차오르는 기회를 놓치지 않기 위해서 미로를 탈출하려고 한다. 한번 움직일때마다 수평 혹은 수직으로 한칸 움직일수있다.

민식이가 미로를 탈출하는데 걸리는 최소한의 이동횟수를 구하는 문제다.

미로에는 문이있고, 

미로는 다음과 같이 구성되어있다.

 

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

풀이

BFS와 비트마스킹을 이용해서 푸는문제다.

문을열때 열쇠를 가지고있는지 없는지 확인해줘야하는데. 열쇠의 종류는 총

a, b, c, d, e, f로 6가지이다. 배열을 

int arr[Y][X][a][b][c][d][e][f];

이런식으로 만들고 열쇠 유무를 확인해야하는데, 가능하다해도 구현하기 어려울것같다.

그래서 열쇠의 유무를 비트마스킹을 통해서 체크해줘야한다.

int check[55][55][1 << 10]; (1 << 7 까지만 해도 된다.)

 

비트마스킹이란, 0과 1을이용해 알고리즘을 푸는? 기법 같은것이다.

 

1 << 10는 1을 왼쪽으로 10만큼 움직인다는 뜻이다. 앞의 연산을 하면,

1000000000과 같이 초기값이 정해진다. (각 자리는 0과 1로만 나타낼수있다.)

 

1 << 10의 각 자리를 알파벳에 대응하면, 문에 해당하는 열쇠의 유무를 쉽게 표현할수있다. 

 

초기값,

- - - - f e d c b a

1 0 0 0 0 0 0 0 0 0

 

열쇠 f를 집었을때,

- - - - f e d c b a

1 0 0 0 1 0 0 0 0 0

 

열쇠 a를 집었을때,

- - - - f e d c b a

1 0 0 0 0 0 0 0 0 1

 

열쇠 a b c 를 집었을때,

- - - - f e d c b a

1 0 0 0 0 0 0 1 1 1

 

기본적인 BFS를 돌리면서 도착한 위치에 문이있다면, 비트연산을 통해 열쇠가 있다면, 다음위치로 이동시키고, 아니라면 이동시키지않는다.

 

key = 1000000000라 할때

 

a열쇠를 집었다고 표시하고 싶다면,

key = key | 1 << int('a' - 96);처럼 사용하면된다.

(a열쇠의 아스키 코드값은 97임 97 - 96을하면 1자리만큼 왼쪽으로 옮겨짐)

그럼 key는 1000000001이 될것이다. 

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/1194%20%EB%8B%AC%EC%9D%B4%20%EC%B0%A8%EC%98%A4%EB%A5%B8%EB%8B%A4%2C%20%EA%B0%80%EC%9E%90./main.cpp

devxb/JJUNalgo