[백준] 14502 연구소

 

 

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

 

1. 백트래킹으로 0,1의 dfs 탐색

2. 해당 그래프를 bfs로 탐색하며 2로 만들어 최대의 갯수를 구함

 

fun main() = with(Scanner(System.`in`)) {
    val n = nextInt()
    val m = nextInt()
    val graph = Array(n, { IntArray(m, { 0 }) })
    val copy_graph = Array(n, { IntArray(m, { 0 }) })
    val isVisited = Array(n, { Array(m, { false }) })

    var ans = 0

    for (i in 0 until n) {
        for (j in 0 until m) {
            graph[i][j] = nextInt()
        }
    }

    fun bfs() {
        val queue = LinkedList<Pair<Int, Int>>()
        val dx = mutableListOf<Int>(-1, 1, 0, 0)
        val dy = mutableListOf<Int>(0, 0, -1, 1)

        for (i in 0 until n) {
            for (j in 0 until m) {
                if (copy_graph[i][j] == 2) {
                    queue.add(Pair(i, j))
                    copy_graph[i][j] = 2
                    isVisited[i][j] = true
                }
            }
        }
        while (queue.isNotEmpty()) {
            val pos = queue.pop()
            for (i in 0 until 4) {
                val nx = pos.first + dx[i]
                val ny = pos.second + dy[i]
                if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue
                if (copy_graph[nx][ny] == 0) {
                    queue.add(Pair(nx, ny))
                    copy_graph[nx][ny] = 2
                    isVisited[nx][ny] = true
                }
            }
        }
        var count = 0
        for(i in 0 until n){
            for(j in 0 until m){
                if(copy_graph[i][j] == 0){
                    count++
                }
            }
        }
        ans = max(ans , count)
    }
    fun wall(cnt: Int) {
        if (cnt == 3) {
            for (i in 0 until n) {
                for (j in 0 until m) {
                    isVisited[i][j] = false
                    copy_graph[i][j] = graph[i][j]
                }
            }
            bfs()
            return
        }

        for (i in 0 until n) {
            for (j in 0 until m) {
                if(graph[i][j] == 0){
                    graph[i][j] = 1
                    wall(cnt + 1)
                    graph[i][j] = 0
                }
            }
        }
    }
    wall(0)
    println(ans)
}