BFS 기본 문제

1012. 유기농배추

배추 지렁이는 인접한 배추들을 이동하며 해충을 잡아 먹는다

밭 군데군데 배추를 심어뒀기 때문에 배추 벌레가 이동할 수 없는 공간이 존재한다

배추밭 전체를 보호하기 위해 필요한 배추 지렁이는 몇마리인가?

-> BFS 기본 유형

 

가로 세로 바꿔 풀어서 약간 헷갈렸다 

import java.io.*
import java.util.*

lateinit var graph: Array<IntArray>
lateinit var visited: Array<BooleanArray>

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val t = readLine().toInt()
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    repeat(t) {
        var st = StringTokenizer(readLine())
        val m = st.nextToken().toInt()
        val n = st.nextToken().toInt()
        val k = st.nextToken().toInt()

        graph = Array(n) { IntArray(m) { 0 } }
        visited = Array(n) { BooleanArray(m) { false } }

        // 탐색할 그래프 만들기
        repeat(k) {
            st = StringTokenizer(readLine())
            val x = st.nextToken().toInt()
            val y = st.nextToken().toInt()
            graph[y][x] = 1
        }

        // bfs
        var count = 0
        for (row in 0 until n) {
            for(col in 0 until m) {
                if (visited[row][col] || graph[row][col] == 0) continue

                bfs(n, m, col, row)
                count++
            }
        }

        bw.write("$count\n")
    }

    bw.close()
}

fun bfs(n: Int, m: Int, startX: Int, startY: Int) {
    val queue = ArrayDeque<Move>()
    val dx = arrayOf(0, 0, -1, 1)
    val dy = arrayOf(1, -1, 0, 0)

    visited[startY][startX] = true
    queue.add(Move(startX, startY))

    while (queue.isNotEmpty()) {
        val current = queue.remove()

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

            if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue
            if (visited[ny][nx] || graph[ny][nx] == 0) continue

            visited[ny][nx] = true
            queue.add(Move(nx, ny))
        }
    }
}

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

 

10026. 적록색약

 

적록색약이 아닌 경우와 적록색약인 경우로 나눠서 총 bfs를 두번 진행한다

적록색약인 경우에는 R과 G를 같은 값으로 취급하는 조건문을 넣어준다

import java.io.*
import java.util.*

lateinit var graph: Array<CharArray>
lateinit var visited1: Array<BooleanArray>
lateinit var visited2: Array<BooleanArray>
private val dx = arrayOf(1, -1, 0, 0)
private val dy = arrayOf(0, 0, -1, 1)

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val n = readLine().toInt()
    graph = Array(n) { CharArray(n) { 'A' } }
    visited1 =  Array(n) { BooleanArray(n) { false } }
    visited2 = Array(n) { BooleanArray(n) { false } }

    // 1. 그래프 채우기
    for (i in 0 until n) {
        val string = readLine()
        var j = 0
        for (c in string) {
            graph[i][j++] = c
        }
    }

    val bw = BufferedWriter(OutputStreamWriter(System.out))
    var count = 0
    // 2. 적록색약이 아닌 사람이 봤을 때
    for (i in 0 until n) {
        for (j in 0 until n) {
            if (visited1[i][j]) continue
            bfs(n, i, j, visited1, false)
            count++
        }
    }

    bw.write("$count ")
    count = 0
    // 3. 적록색약인 사람이 봤을때
    for (i in 0 until n) {
        for (j in 0 until n) {
            if (visited2[i][j]) continue
            bfs(n, i, j, visited2, true)
            count++
        }
    }

    bw.write("$count")
    bw.close()
}

private fun bfs(n: Int, startR: Int, startC: Int, visited: Array<BooleanArray>, isColorWeakness: Boolean) {
    val queue = ArrayDeque<Move>()
    val c = graph[startR][startC]
    visited[startR][startC] = true
    queue.add(Move(startR, startC))

    while (queue.isNotEmpty()) {
        val current = queue.remove()
        for (i in 0 until 4) {
            val nx = current.x + dx[i]
            val ny = current.y + dy[i]

            if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue

            if (visited[nx][ny] || !check(isColorWeakness, c, graph[nx][ny])) continue

            visited[nx][ny] = true
            queue.add(Move(nx, ny))
        }
    }
}

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

private fun check(isColorWeakness: Boolean, c1: Char, c2: Char): Boolean {
    if (c1 == c2)
        return true

    if (isColorWeakness) {
        if (c1 == 'R' && c2 == 'G')
            return true
        if (c1 == 'G' && c2 == 'R')
            return true
    }

    return false
}

7569. 토마토

3차원 공간 bfs를 통해 거리 구하기

- 익은 토마토가 없을 경우

- 익어있지 않은 토마토가 있을 경우

- 이미 다 익어있을 경우 등을 생각해서 처리하기

import java.io.*
import java.util.*
import kotlin.system.exitProcess

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    var st = StringTokenizer(readLine())
    val m = st.nextToken().toInt() // 가로
    val n = st.nextToken().toInt() //  세로
    val h = st.nextToken().toInt() // 높이
    val graph = Array(h) { Array(n) { IntArray(m) {-1} } }
    val tomato = Array(h) { Array(n) { IntArray(m) {-1} } }
    var count = 0
    var days = 0
    val queue = ArrayDeque<Move>()

    for (height in 0 until h) {
        for (row in 0 until n) {
            st = StringTokenizer(readLine())
            for (col in 0 until m) {
                val current = st.nextToken().toInt()
                graph[height][row][col] = current
                if (current == 1) {
                    queue.add(Move(height, row, col))
                    tomato[height][row][col] = 0 // 익은 토마
                    count++
                }
                if (current == -1) {
                    tomato[height][row][col] = -2 // 빈 공간
                }
            }
        }
    }
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    if (count == 0) { // 익은 토마토가 하나도 없을 경우
        bw.write("-1")
        bw.close()
        exitProcess(0)
    }

    val dx = arrayOf(1, -1, 0, 0, 0, 0) // 위 아래 왼쪽 오른쪽 앞 뒤
    val dy = arrayOf(0, 0, -1, 1, 0, 0)
    val dz = arrayOf(0, 0, 0, 0, 1, -1)

    for (height in 0 until h) {
        for (row in 0 until n) {
            for (col in 0 until m) {
                // bfs
                while (queue.isNotEmpty()) {
                    val current = queue.remove()

                    for (i in 0 until 6) {
                        val nx = current.x + dx[i]
                        val ny = current.y + dy[i]
                        val nz = current.z + dz[i]

                        if (nx < 0 || nx >= n || ny < 0 || ny >= m || nz < 0 || nz >= h) continue
                        if (graph[nz][nx][ny] == -1 || tomato[nz][nx][ny] != -1) continue

                        tomato[nz][nx][ny] = tomato[current.z][current.x][current.y] + 1
                        queue.add(Move(nz, nx, ny))
                        days = tomato[current.z][current.x][current.y] + 1
                    }
                }
            }
        }
    }

    for (height in 0 until h) {
        for (row in 0 until n) {
            for (col in 0 until m) {
                if (tomato[height][row][col] == -1) { // 익지 않은 토마토가 있을 경우
                    bw.write("-1")
                    bw.close()
                    exitProcess(0)
                }
            }
        }
    }

    bw.write("$days")
    bw.close()
}

data class Move(val z: Int, val x: Int,val y: Int)

 

7562. 나이트의 이동

이동 가능한 칸이 좀 귀찮게 생겼다 

x 가로 y 세로

2, -2	2, -1	2, 0	2, 1	2, 2
1, -2	1, -1	1, 0	1, 1	1, 2
0, -2	0, -1	0, 0	0, 1	0, 2
-1, -2	-1, -1	-1, 0	-1, 1	-1, 2
-2, -2	-2, -1	-2, 0	-2, 1	-2, 2

나이트가 이동할 수 있는 칸

(2, -1), (2, 1), (1, -2), (1, 2), (-1, -2), (-1, 2), (-2, -1), (-2, 1)

dx = arrayOf (2, 2, 1, 1, -1, -1, -2, -2)

dy = arrayOf (-1, 1, -2, 2, -2, 2, -1, 1)

 

나이트가 목표지점에 도달할 때까지 탐색을 진행한다

import java.io.*
import java.util.*

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val t = readLine().toInt()
    val dx = arrayOf(2, 2, 1, 1, -1, -1, -2, -2)
    val dy = arrayOf(-1, 1, -2, 2, -2, 2, -1, 1)
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    repeat(t) {
        val l = readLine().toInt() // 체스판 한변의 길이
        val queue = ArrayDeque<Location>()
        val dist = Array(l) { IntArray(l) { -1 } }

        var st = StringTokenizer(readLine())
        val current = Location(st.nextToken().toInt(), st.nextToken().toInt())
        dist[current.x][current.y] = 0
        queue.add(current)

        st = StringTokenizer(readLine())
        val destination = Location(st.nextToken().toInt(), st.nextToken().toInt())

        // bfs
        while (queue.isNotEmpty()) {
            val location = queue.remove()

            // 목표 지점 도달
            if (location == destination) {
                bw.write("${dist[location.x][location.y]}\n")
            }

            for (m in 0 until 8) {
                val nx = location.x + dx[m]
                val ny = location.y + dy[m]

                if (nx < 0 || ny < 0 || nx >= l || ny >= l) continue
                if (dist[nx][ny] != -1) continue

                dist[nx][ny] = dist[location.x][location.y] + 1
                queue.add(Location(nx, ny))
            }
        }
    }

    bw.close()
}

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

 

5427. 불

 

불 bfs -> 상근이 bfs

 

어떤 위치에 불이 도달하는 시간이 상근이가 도달하는 시간보다 적을 경우 상근이는 해당 위치를 통과할 수 없다

상근이는 주어진 공간을 벗어난 경우 탈출했다고 볼 수 있다

import java.io.*
import java.util.*

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val t = readLine().toInt()
    val dx = arrayOf(1, -1, 0, 0)
    val dy = arrayOf(0, 0, -1, 1)
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    repeat(t) {
        val st = StringTokenizer(readLine())
        val w = st.nextToken().toInt()
        val h = st.nextToken().toInt()

        val map = Array(h) { CharArray(w)}

        val fireQueue = ArrayDeque<Location>()
        val fireDist = Array(h) { IntArray(w) { -1 } }

        val sgQueue = ArrayDeque<Location>()
        val sgDist = Array(h) { IntArray(w) { -1 } }

        // 지도 만들기
        for (i in 0 until h) {
            val s = readLine()
            s.forEachIndexed { j, c ->
                map[i][j] = c
                if (c == '*') {
                    fireQueue.add(Location(i, j))
                    fireDist[i][j] = 0
                }
                if (c == '@') {
                    sgQueue.add(Location(i, j))
                    sgDist[i][j] = 0
                }
            }
        }

        // 불 bfs
        while (fireQueue.isNotEmpty()) {
            val current = fireQueue.remove()

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

                if (nx in 0 until h && ny in 0 until w) {
                    if (!map[nx][ny].isWall() && fireDist[nx][ny] == -1) {
                        fireDist[nx][ny] = fireDist[current.x][current.y] + 1
                        fireQueue.add(Location(nx, ny))
                    }
                }
            }
        }

        // 상근 bfs
        while (sgQueue.isNotEmpty()){
            val current = sgQueue.remove()

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

                if (nx < 0 || nx >= h || ny < 0 || ny >= w) {
                    bw.write("${sgDist[current.x][current.y] + 1}\n")
                    return@repeat
                }

                if (map[nx][ny].isWall() || sgDist[nx][ny] != -1) continue
                if (fireDist[nx][ny] != -1 && fireDist[nx][ny] <= sgDist[current.x][current.y] + 1) continue

                sgDist[nx][ny] = sgDist[current.x][current.y] + 1
                sgQueue.add(Location(nx, ny))
            }
        }

        bw.write("IMPOSSIBLE\n")
    }
    bw.close()
}

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

private fun Char.isWall() = this == '#'