[백준 11967번] [Kotlin] 불켜기

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

11967번: 불켜기

 

난이도 : 골드 2
태그 : 그래프탐색, 그래프이론, 너비우선탐색

 

 

설명

한 좌표에 다른 좌표의 불을 켤 수 있는 스위치가 있습니다. 복수개일 수 있으며,

스위치를 총 몇 개나 작동시킬 수 있는지(불을 킬 수 있는지)를 구하는 문제입니다.

 

BFS를 사용하면 될 것 같지만,

스위치를 켜서 갈 수 있는 좌표가 늘어남에 따라,

해당 좌표와 인접한 좌표를 이미 탐색했을 때, BFS의 큐에 어떻게 추가할지 고민을 많이 했었습니다.

혹시나 해서 더 이상 스위키를 키지 않을 때 까지(맵이 업데이트 되지 않을 때 까지)

BFS를 반복적으로 돌려볼까? 싶었는데, n의 범위가 100밖에 되지 않으므로 충분히 가능하다 판단하였습니다.

 

각각의 맵에는 갈 수 있는지(불이 켜져 있는지)에 대한 정보를 담고있는 lightOnMap과,

각 좌표에 있는 스위치 정보를 담고있는 switchMap 가 있습니다.

좌표를 담을 클래스 Node(x,y)를 하나 만들어,

switchMap의 각 좌표는 Queue<Node>로,

switch[3][4] = Queue { {2,3}, {1,4} }  일 경우,

(3,4) 좌표에 있는 스위치는 (2,3)과 (1,4) 방 불을 켤 수 있는 스위치가 있다. 라는 의미입니다.

 

이제, BFS 탐색을 진행하며 한 BFS 내에

하나라도 방의 불을 켰다면 맵이 업데이트 된 것이므로 BFS를 새롭게 돌립니다.

이 과정을 더 이상 불을 켤 방이 없을 때 까지 (맵이 업데이트 되지 않을 때 까지) 반복합니다.

 

 

 

소스코드

import java.util.LinkedList
import java.util.Queue

data class Node(val x: Int, val y: Int)

val dx = intArrayOf(1, 0, -1, 0)
val dy = intArrayOf(0, 1, 0, -1)

var n = 0
var m = 0
var cnt = 1

lateinit var lightOnMap: Array<Array<Boolean>>
lateinit var switchMap: Array<Array<Queue<Node>>>

fun main() = with(System.`in`.bufferedReader()) {
    val nm = readLine().split(" ").map { it.toInt() }
    n = nm[0]
    m = nm[1]

    lightOnMap = Array(n) { Array(n) { false } }
    lightOnMap[0][0] = true

    switchMap = Array(n) { Array(n) { LinkedList() } }

    repeat(m) {
        val (switchRoomX, switchRoomY, lightRoomX, lightRoomY) = readLine().split(" ").map { it.toInt() - 1 }
        switchMap[switchRoomX][switchRoomY].add(Node(lightRoomX, lightRoomY))
    }

    bfs()

    println(cnt)
}

fun bfs() {
    val q = LinkedList<Node>() as Queue<Node>
    val visited = Array(n) { Array(n) { false } }
    visited[0][0] = true

    q.offer(Node(0, 0))

    var isLightOn = false

    while (q.isNotEmpty()) {
        val target = q.poll()

        while (switchMap[target.x][target.y].isNotEmpty()) {
            val lightOnRoom = switchMap[target.x][target.y].poll()
            if (!lightOnMap[lightOnRoom.x][lightOnRoom.y]) {
                isLightOn = true
                lightOnMap[lightOnRoom.x][lightOnRoom.y] = true
                cnt++
            }
        }

        for (i in 0 until 4) {
            val nx = target.x + dx[i]
            val ny = target.y + dy[i]

            if (nx !in 0 until n || ny !in 0 until n || !lightOnMap[nx][ny] || visited[nx][ny]) continue

            q.offer(Node(nx, ny))
            visited[nx][ny] = true
        }
    }

    if(isLightOn) bfs()
}

 

BFS는 하나라도 불이 켜진 방이 있을 시 (isLightOn 이 true일 경우) 재귀적으로 bfs()를 호출합니다.

물론 main 함수 내 반복문을 통해 구현해도 됩니다.

 

 

 

후기

상당히 애먹었던 문제였습니다.

지문을 꼼꼼히 읽지 않아 한 좌표에 하나의 스위치만 있는 줄 알고 삽질을 꽤나 했습니다.

뒤늦게 한 좌표에 복수개의 스위치가 있을 수 있다는 문구를 읽고 간신히 풀었네요.