<백준> 달이 차오른다, 가자.(Gold 1)
[백준]
https://www.acmicpc.net/problem/1194
[깃허브]
최종 프로젝트가 마무리되고 드디어 다시 알고리즘 문제를 풀 여유가 생겼다.
물론 밀렸던 집안일 하랴... 이력서 준비하랴... 이것저것 하다보니 아침에 하려고 했던 일정이 망가져서 밤 늦게 하고 있지만 다시 손을 대서 할 수 있다는게 어디인가 싶다.(감사한 마음 뿐...)
그렇게 오늘 손을 댄 문제는 친구에게 추천받은 백준 문제였다.
내가 BFS, DFS, DP에 너무 약하다고 하니까 바로 추천해준 문제로 기본 BFS에 비트마스킹까지 섞여있다고 미리 말해주더라
BFS만 있었으면 좀 겁을 덜 먹었을텐데 비트마스킹이 있다고 하니까 겁을 더 먹었다.
※ 비트마스킹
정수의 이진수 표현을 자료구조로 쓰는 기법
- 비트 연산자
a and b : a의 모든 비트와 b의 모든 비트를 AND 연산
a or b : a의 모든 비트와 b의 모든 비트를 OR 연산
a xor b : a의 모든 비트와 b의 모든 비트를 XOR 연산
a.inv() : a의 모든 비트에 NOT 연산
a shl 1 : a의 모든 비트를 왼쪽으로 1칸 이동
a shr 1 : a의 모든 비트를 오른쪽으로 1칸 이동
- 응용하는 영역
집합의 표현, 원소 추가, 원소 삭제, 원소 토글, 집합 연산, 부분 집합 순회 등...
문제를 보면서 다른 것보다 가장 고민이 되는 건 '어떻게 찾은 열쇠를 저장하고 분기를 나눠야하나?'였다.
뭔가 이부분이 비트마스킹을 쓰는 거 같은데 감이 잘 오지 않았다.
그래서 이번에는 고민을 하다가 바로 블로그를 돌아다녔다.
그렇게 해서 알게 된 건 visited 변수를 3차원 배열로 사용하는 것과 열쇠 하나하나를 한 비트로 취급해서 비트마스킹을 사용하는 것이었다.
그렇게 하니까 열쇠 개수에 따른 모든 분기를 저장할 수 있게 되더라
전에도 이런 문제를 봤었던 거 같은데 기억이 제대로 나지는 않는다.
풀기도 했었던 거 같은데...
익숙한 BFS의 형태였고 다른 것은 비트 연산자를 사용하는 부분이었다.
keys and (1 shl (maze[new_r][new_c] - 'A' + 1))
keys or (1 shl (maze[new_r][new_c] - 'a' + 1))또한 Data Class를 사용하는 부분이었다.
이런 문제(관리해야하는 프로퍼티가 여러개)를 풀 때는 Data Class를 사용하는 게 확실히 편리한 거 같다.
또한 한 줄에 두 개의 값이 있을 때 한번에 받는 방법도 알게 되었다.
val (n, m) = readLine().split(' ').map { it.toInt() }
출구에 도착하면 현재 cnt에 1을 더해 반환하고
문을 만나면 열쇠가 있을 때 큐에 추가하고
열쇠를 찾으면 열쇠 리스트를 갱신한 다음 큐에 추가하고
그냥 길이면 큐에 추가한다.
정말 딱 비트마스킹만 추가된 문제였고 여러가지로 응용해볼만한 문제유형인 거 같다.
꼭 복습을 해야겠다.(태그에 추가완료)
뭔가 앞으로 이런 문제를 많이 보게 될 거 같다.
3차원 배열로 하니까 더 케이스가 넓어진다.
그리고 뭔가 열쇠가 1회용이었다면 이 문제가 더 어려웠을 거 같다는 생각이 든다.
해당 방법으로 작성한 코드는 다음과 같다.
import java.util.LinkedList
val dy = arrayOf(0, 1, 0, -1)
val dx = arrayOf(1, 0, -1, 0)
val visited = Array(1 shl 7) { Array(50) { BooleanArray(50) } }
// BFS에서 사용할 순간순간의 정보가 담긴 데이터 클래스
data class Pos(
val r: Int,
val c: Int,
val key: Int,
val cnt: Int
)
fun main() = with(System.`in`.bufferedReader()) {
// 미로의 가로 세로 길이
val (n, m) = readLine().split(' ').map { it.toInt() }
// 민식이의 row 시작 위치
var sr = 0
// 민식이의 column 시작 위치
var sc = 0
// 미로 모양
val maze = Array(n) { r ->
val row = readLine()
CharArray(m) { c ->
var pos = row[c]
if (row[c] == '0') {
sr = r
sc = c
pos = '.'
}
pos
}
}
println(bfs(sr, sc, n, m, maze))
close()
}
fun bfs(sr: Int, sc: Int, n: Int, m: Int, maze: Array<CharArray>): Int {
// 시작위치 큐에 넣음
val q = LinkedList<Pos>()
q.add(Pos(sr, sc, 1, 0))
visited[1][sr][sc] = true
while (q.isNotEmpty()) {
// 큐에서 하나 뺌
val cur = q.poll()
// 네 방향 체크
for (i in 0 until 4) {
val new_r = cur.r + dy[i]
val new_c = cur.c + dx[i]
var keys = cur.key
// 패스하는 조건들
if (new_r !in 0 until n || new_c !in 0 until m) continue
if (visited[keys][new_r][new_c]) continue
if (maze[new_r][new_c] == '#') continue
// 출구인 경우
if (maze[new_r][new_c] == '1') return cur.cnt + 1
if (maze[new_r][new_c] in 'A'..'F') { // 문을 만난 경우
if (keys and (1 shl (maze[new_r][new_c] - 'A' + 1)) != 0) { // 열쇠가 있다면 큐에 추가
q.add(Pos(new_r, new_c, keys, cur.cnt + 1))
visited[keys][new_r][new_c] = true
} else { // 열쇠가 없다면 패스
continue
}
} else if (maze[new_r][new_c] in 'a'..'f') { // 열쇠를 찾으면 열쇠 리스트 갱신하고 큐에 추가
keys = keys or (1 shl (maze[new_r][new_c] - 'a' + 1))
q.add(Pos(new_r, new_c, keys, cur.cnt + 1))
visited[keys][new_r][new_c] = true
} else { // 그 외에는 그냥 큐에 추가
q.add(Pos(new_r, new_c, keys, cur.cnt + 1))
visited[keys][new_r][new_c] = true
}
}
}
// 미로 탈출 방법이 없는 경우
return -1
}
참고)