BOJ 달이 차오른다, 가자 문제 자바(java) 풀이
문제 정리
- 미로를 탈출하려 한다. 미로는 다음과 같이 구성되어 있다.
- 빈 곳: 언제나 이동 가능(.)
- 벽: 절대 이동 불가(#)
- 열쇠: 언제나 이동할 수 있다. 이 곳에 처음 들어가면 열쇠를 잡는다(a - f)
- 문: 대응하는 열쇠가 있을 때만 이동 가능(A - F)
- 민식이 위치: 빈 곳, 현재 서 있는 곳 (숫자 0)
- 출구: 달이 차오르기 때문에, 민식이가 가야하는 곳. 탈출로(숫자 1)
- 민식이는 수평, 수직으로 이동가능하다. 탈출하는데 걸리는 이동 횟수의 최솟값을 구하시오
- 열쇠와 문은 여러 개일 수도 있다.
- 문에 대응하는 열쇠가 없을수도 있다.
- 0은 1개, 1은 적어도 한 개 있다. 열쇠는 여러 번 사용할 수 있다.
문제 접근
(이 문제는 장기하의 달이 차오른다, 가자를 들으며 풀었습니다 ㅋㅋㅋㅋㅋㅋ)
문제를 딱 보고 bfs로 풀면 되겠다고 생각했습니다. ( 아니 그 전에 웃기다고 생각했습니다 )
그러고 bfs로 돌렸습니다. key는 boolean 배열에 넣어 check 하였습니다.
그런데 계속 -1이 나오더라구요 ㅠㅠ
보니까 key를 가지고 왔던 길을 다시가야했는데 그때 이미 다른 경우에서 지나쳐가서 갈 수가 없었습니다.
그래서 3차원 배열로 4방향으로도 방문을 체크하려했지만 역시 실패..
다시 방문 횟수를 10회까지 늘려보았는데도 실패를 맛보았습니다.
질문검색 게시판을 보다가 오!! 했습니다.
3차원 배열까진 맞았지만 키를 가지고 방문여부를 체크함을....
문제 풀이
- 입력을 받습니다. 민식이의 위치는 따로 저장합니다.
- 민식이의 위치로부터 bfs 탐색을 합니다.
- 방문 체크를 할 3차원 배열을 만드빈다 [x][y][key]
[x][y][key]는 x,y에 방문할때 어떤 key를 가지고 있는 상태로 방문했는지 입니다.
예를들어 a번 키를 가진 상태로 방문했다면 [x][y][0] = true가 됩니다.
- 4방향으로 탐색을 합니다. 유효한 위치이고 방문하지 않았다면 miro를 체크합니다.
- 빈 곳 or 출구 or 민식이가 있던 곳 일 경우: 방문처리하고 queue에 넣습니다.
- 열쇠가 있는 곳: bit 연산을 통해 key를 가지게 되었음을 체크합니다. 이때 다음 방향 탐색시에 중복되지 않도록 값을 복사해서 연산합니다.
- 문에 도달: 해당하는 열쇠가 있는지 계산 후 있다면 방문 처리 후 큐에 넣습니다.
- 큐가 빌때까지 반복하며, 1에 도달한 경우 거리를 min 값과 비교하여 갱신합니다.
- bfs 함수가 끝난후 min 값이 초기값 그대로이면 -1, 아니면 min 값을 출력합니다.
비트 마스킹
- key 가지고 있음 처리
1.1 우선 key를 copy에 복사합니다.
1.2 (miro[dx][dy] - 'a'): 우선 아스키 코드 값 'a'를 빼서 숫자로 변환합니다.
1.3 1 << (miro[dx][dy] - 'a'): 변환된 숫자를 가지고 오른쪽으로 bit shift 합니다. 예를들어 key가 f였다면
1이 5칸 이동되어 100000이 됩니다(이진수)
1.4 기존에 가지고 있던 key와 Or연산을 하면 가지고 있는 key에 새로운 key를 추가할 수 있습니다.
예를들어 이미전에 a키를 가지고 있었다면 000001이고 거기에 100000를 or 하면 1000001이 됩니다.
첫 번째 bit는 'a' key, 6번째 bit는 'f' key를 나타냅니다.
- key 가지고 있는지 여부
1.1 1 << (miro[dx][dy] - 'A')): 숫자로 변환후 오른쪽으로 bit shift 연산을 합니다. 이게 바로 문을 나타냅니다. 예를들어 'B'였다면 000010이 되어 문이 B임을 알 수 있습니다.
1.2 key 값과 & 연산합니다. & 연산 후 0이 아닌 door 값과 같다면 key가 있는 것이므로 방문합니다.
예를들어 door와 & 연산하면 2 번째 비트를 제외한 나머지 비트는 우선 모두 0입니다. 그런데 key의 2번째 bit가 1이라면('b'key를 가지고 있다면면 2번째 bit만 1이 됩니다. 즉 door와 같습니다.
만약 'b' key를 가지고 있지 않아 2번째 bit가 0이라면 & 연산 후 0이 됩니다.
문제풀이 소감
약간 난이도가 있는 bfs, dfs는 우선 방문처리 여부가 관건인 것 같습니다
어제 풀었던 벽 부수고 이동하기도 방문처리를 어떻게 하냐가 문제였고 생각보다 쉽지 않았습니다
이번이 이러한 유형의 2번째 문제 였습니다.
3차원 배열로 방문처리하면 되겠다 생각은 했지만 bitmasking을 쉽게 떠올리지는 못했습니다.
이러한 스킬도 꼭 머리 속에 넣어두자...!!!
백준 1194번 달이 차오른다, 가자 자바 코드