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

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

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

 

난이도 : 골드 1

 

Set을 이용한 BFS로 문제를 풀다가 오류를 만났습니다. 도저히 방법이 없어 검색해보니 비트 마스킹으로 쉽게 풀 수 있는 문제였습니다.

방문 검사는 3차원 배열을 통해 진행합니다. a~f까지 6개의 열쇠가 있으므로 [N][M][111111]의 크기를 가집니다.

비트 연산을 통해 key를 저장하고 문을 여는 것이 목표입니다.

key를 넣는 과정은 or 연산(1 << 열쇠 - 'a')이고 문을 여는 과정은 and 연산(1 << 문 - 'A')입니다.

 

a, c 열쇠를 넣고 B, C 문을 열어보겠습니다.

초기값은 000000(0)입니다. a는 1 << 0 = 1이므로 or 연산을 하면 key 값은 000001(1)이 됩니다.

c는 1 << 2 = 4이므로 or 연산을 하면 key 값은 000101(5)이 됩니다.

 

B의 문은 1 << 1 = 000010(2)의 값을 가집니다. 000101 & 000010 == 0 이므로 b가 없기 때문에 통과할 수 없습니다.

C의 문은 1 << 2 = 000100(4)의 값을 가집니다. 000101 & 000100 != 0 이므로 c를 가지고 있어 통과할 수 있습니다.

 

이를 통해 현재의 key값으로 방문 여부를 확인할 수 있습니다.

---

전역 변수

int n, m = 맵의 크기

char map[][] = 입력으로 주어진 맵

int dx[], dy [] = 4방향으로 이동할 수 있는 배열

 

메소드

void main

입력을 받고 map을 구성합니다. 그리고 출발 위치를 x, y에 저장합니다.

(escape 호출)

 

void escape

큐를 만들고 한 턴을 구분하는 -1, -1을 넣어주고 방문을 관리하는 visit배열을 선언합니다.

BFS를 진행하며 현재 위치가 1이거나 큐가 빌 때까지 진행합니다.

4방향으로 이동하며 유효한 범위에서 열쇠를 만나면 key에 넣어줍니다.

만약 문을 만난다면 열쇠와 비교하고 열쇠를 가지고 있다면 방문합니다.

(check 호출)

 

boolean check

현재 범위가 유효하고 이 칸에 '#'(벽)이 없는지 확인해줍니다.

 

class Point

현재 좌표 x, y와 현재 키 값을 저장합니다.