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

 

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

---

비트 연산자 + BFS 문제입니다.

 

A~F는 6개의 문자로 

{공집합, ... , {a,b,c,d,e,f} } 까지의 부분집합은 2^6 = 64개로 나타낼 수 있습니다.

총 64개의 state가 존재한다고 표현하겠습니다. 

그래서 [64][N][M] 만큼의 방문(상태)배열이 존재하게 됩니다.

 

그러면 각 칸을 순회할 때 가지고 있어야 할 정보는 아래와 같이 네 가지 정보입니다.

{ 현재 STATE(0~64), Y좌표, X좌표, MOVE_CNT }

 

열쇠칸을 만났다면 OR 연산자를 통해 현재 STATE에 특정 열쇠를 더해줍니다.

int NEW_STATE = NOW_STATE | (1<< NOW_KEY)

 

문 칸을 만났다면 AND 연산자를 통해 현재 STATE로 이 문을 열 수 있는지 판단해줍니다.

int RESULT = NOW_STATE & (1<< NOW_DOOR)

RESULT가 양수라면 문을 열 수 있고, RESULT가 0이라면 문을 열 수 없습니다.

---

코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ1194.cc