[백준] 9328번:열쇠 - Kotlin/코틀린

jibmin jung·2022년 4월 30일
0

백준 9328번 열쇠

출처 - https://www.acmicpc.net/problem/9328

문제

상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 필요하다. 상근이는 일부 열쇠를 이미 가지고 있고, 일부 열쇠는 빌딩의 바닥에 놓여져 있다. 상근이는 상하좌우로만 이동할 수 있다.

상근이가 훔칠 수 있는 문서의 최대 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 수는 100개를 넘지 않는다.

각 테스트 케이스의 첫째 줄에는 지도의 높이와 너비 h와 w (2 ≤ h, w ≤ 100)가 주어진다. 다음 h개 줄에는 빌딩을 나타내는 w개의 문자가 주어지며, 각 문자는 다음 중 하나이다.

'.'는 빈 공간을 나타낸다.
'*'는 벽을 나타내며, 상근이는 벽을 통과할 수 없다.
'$'는 상근이가 훔쳐야하는 문서이다.
알파벳 대문자는 문을 나타낸다.
알파벳 소문자는 열쇠를 나타내며, 그 문자의 대문자인 모든 문을 열 수 있다.
마지막 줄에는 상근이가 이미 가지고 있는 열쇠가 공백없이 주어진다. 만약, 열쇠를 하나도 가지고 있지 않는 경우에는 "0"이 주어진다.

상근이는 처음에는 빌딩의 밖에 있으며, 빌딩 가장자리의 벽이 아닌 곳을 통해 빌딩 안팎을 드나들 수 있다. 각각의 문에 대해서, 그 문을 열 수 있는 열쇠의 개수는 0개, 1개, 또는 그 이상이고, 각각의 열쇠에 대해서, 그 열쇠로 열 수 있는 문의 개수도 0개, 1개, 또는 그 이상이다. 열쇠는 여러 번 사용할 수 있다.

출력

각 테스트 케이스 마다, 상근이가 훔칠 수 있는 문서의 최대 개수를 출력한다.

풀이

문제 그대로 구현하면 되는 구현 문제이다.
BFS를 이용해서 탐색을 진행한다.
열쇠는 해쉬셋에 저장해두었다.

BFS 진행 중 문서를 만나면 답을 증가시키고,
열쇠를 만나면 해쉬셋에 넣어주고,
문을 만나면 열쇠가 있는지 해쉬셋을 확인한 뒤 있으면 진행하고, 없으면 나중에 열쇠를 주울 경우에 대비해 큐에 넣어서 해당 문에서 시작할 수 있도록 한다.

큐에 있는 모든 노드가 열쇠가 없는 문일 경우, bfs 루프를 깨고 나와주도록 했다.

어떤 위치가 문이면 'A'~'Z' 의 값을, 열쇠면 'a'~'z'의 값을 갖는다.
이것은 코틀린의 범위 표현 "in"과 ".."을 쓰면 편하게 확인할 수 있다.

fun Char.isKey(): Boolean = this in 'a'..'z'
fun Char.isDoor(): Boolean = this in 'A'..'Z'

이렇게 확장함수를 만들어두면 코드가 깔끔하다.

열쇠 저장의 경우 해쉬셋을 이용했지만, 비트마스크를 이용하면 더 빠르고 가볍고 좋다.

그리고 처음에 평면도를 입력받을 때,
배열을 h+2 * w+2 사이즈로 하고, 건물 주변을 '.'으로 둘러싸도록 하면,
그렇게 하지 않았을 경우 진입점을 하나하나 확인해주는 것에 비해,
(0,0) 포인트만 큐에 넣어주면 알아서 진입점으로 들어가기 때문에 훨씬 간결한 코드를 짤 수 있다.

코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
import kotlin.collections.HashSet

val sb = StringBuilder()
val dx = arrayOf(1, 0, -1, 0)
val dy = arrayOf(0, 1, 0, -1)
var cnt = 0
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    repeat(readLine().toInt()) {
        val (h, w) = readLine().split(" ").map { it.toInt() }
        val arr = Array(h+2) {
            if(it in 1..h) ('.'+readLine().trim()+'.').toCharArray()
            else CharArray(w+2){'.'}
        }
        val hs = HashSet<Char>(27) //0, a~z 총 27개 (0은 열쇠가 아니지만 상관없다)
        hs.addAll(readLine().toCharArray().asIterable())
        cnt = 0
        bfs(arr, hs, h, w)
        sb.append(cnt).append("\n")

    }
    println(sb)
}

fun bfs(arr: Array<CharArray>, hs: HashSet<Char>, h: Int, w: Int) {
    val q = LinkedList<Pair<Int, Int>>()
    val visit = Array(h+2) { BooleanArray(w+2) }
    q.offer(Pair(0,0))
    while (!q.isEmpty()) {
        val qs = q.size
        var flag = true //큐에 모든 노드가 열 수 없는 문인지 확인하기 위한 플래그
        repeat(qs) {
            val (x, y) = q.poll()
            if (arr[x][y].isDoor() && hs.contains(arr[x][y].lowercaseChar()).not()) {
                q.offer(Pair(x, y))
                return@repeat
            }
            if (arr[x][y] == '$') cnt++
            flag = false //열 수 없는 문이 아닌 노드가 있으므로 플래그 변경
            for (k in 0..3) {
                val nx = x + dx[k]
                val ny = y + dy[k]
                if ((nx !in 0 .. h+1) || (ny !in 0 .. w+1) || visit[nx][ny]) continue
                if (arr[nx][ny] == '.' || arr[nx][ny] == '$') {
                    q.offer(Pair(nx, ny))
                    visit[nx][ny] = true
                }
                if (arr[nx][ny].isKey()) {
                    hs.add(arr[nx][ny])
                    q.offer(Pair(nx, ny))
                    visit[nx][ny] = true
                }
                if (arr[nx][ny].isDoor()) {
                    q.offer(Pair(nx, ny))
                    visit[nx][ny] = true
                }
            }
        }
        if (flag) break
    }
}

fun Char.isKey(): Boolean = this in 'a'..'z'
fun Char.isDoor(): Boolean = this in 'A'..'Z'
import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
import kotlin.collections.HashSet

val sb = StringBuilder()
val dx = arrayOf(1, 0, -1, 0)
val dy = arrayOf(0, 1, 0, -1)
var cnt = 0
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    repeat(readLine().toInt()) {
        val (h, w) = readLine().split(" ").map { it.toInt() }
        val arr = Array(h) { CharArray(w) }
        for (i in 0 until h) {
            arr[i] = readLine().toCharArray()
        }
        val hs = HashSet<Char>(27)
        hs.addAll(readLine().toCharArray().asIterable())
        cnt = 0
        bfs(arr, hs, h, w)
        sb.append(cnt).append("\n")

    }
    println(sb)
}

fun bfs(arr: Array<CharArray>, hs: HashSet<Char>, h: Int, w: Int) {
    val q = LinkedList<Pair<Int, Int>>()
    val visit = Array(h) { BooleanArray(w) }
    for (i in arr.indices) {
        val temp1 = arr[i][0]
        val temp2 = arr[i][w - 1]
        if (temp1 == '.' || temp1 == '$' || temp1.isDoor() || temp1.isKey()) {
            if(temp1.isKey()) hs.add(arr[i][0])
            q.offer(Pair(i, 0))
            visit[i][0] = true
        }
        if (temp2 == '.' || temp2 == '$' || temp2.isDoor() || temp2.isKey()) {
            if(temp2.isKey()) hs.add(arr[i][w-1])
            q.offer(Pair(i, w - 1))
            visit[i][w - 1] = true
        }
    }
    for (i in 1 until w - 1) {
        val temp1 = arr[0][i]
        val temp2 = arr[h - 1][i]
        if (temp1 == '.' || temp1 == '$' || temp1.isDoor() || temp1.isKey()) {
            if (temp1.isKey()) hs.add(arr[0][i])
            q.offer(Pair(0, i))
            visit[0][i] = true
        }
        if (temp2 == '.' || temp2 == '$' || temp2.isDoor() || temp2.isKey()) {
            if (temp2.isKey()) hs.add(arr[h - 1][i])
            q.offer(Pair(h - 1, i))
            visit[h - 1][i] = true
        }
    }
    while (!q.isEmpty()) {
        val qs = q.size
        var flag = true
        repeat(qs) {
            val (x, y) = q.poll()
            if (arr[x][y].isDoor() && hs.contains(arr[x][y].lowercaseChar()).not()) {
                q.offer(Pair(x, y))
                return@repeat
            }
            if (arr[x][y] == '$') cnt++
            flag = false
            for (k in 0..3) {
                val nx = x + dx[k]
                val ny = y + dy[k]
                if ((nx !in 0 until h) || (ny !in 0 until w) || visit[nx][ny]) continue
                if (arr[nx][ny] == '.' || arr[nx][ny] == '$') {
                    q.offer(Pair(nx, ny))
                    visit[nx][ny] = true
                }
                if (arr[nx][ny].isKey()) {
                    hs.add(arr[nx][ny])
                    q.offer(Pair(nx, ny))
                    visit[nx][ny] = true
                }
                if (arr[nx][ny].isDoor()) {
                    q.offer(Pair(nx, ny))
                    visit[nx][ny] = true
                }
            }
        }
        if (flag) break
    }
}

fun Char.isKey(): Boolean = this in 'a'..'z'
fun Char.isDoor(): Boolean = this in 'A'..'Z'

결과

위가 "."으로 둘러싼 평면도
아래가 그냥 평면도다.

profile
이것저것 안드로이드

0개의 댓글