[백준/BOJ] 1012번: 유기농 배추

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

1012번: 유기농 배추

문제

차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. 한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있는 것이다.

한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어 놓았다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다. 예를 들어 배추밭이 아래와 같이 구성되어 있으면 최소 5마리의 배추흰지렁이가 필요하다. 0은 배추가 심어져 있지 않은 땅이고, 1은 배추가 심어져 있는 땅을 나타낸다.

1	1	0	0	0	0	0	0	0	0
0	1	0	0	0	0	0	0	0	0
0	0	0	0	1	0	0	0	0	0
0	0	0	0	1	0	0	0	0	0
0	0	1	1	0	0	0	1	1	1
0	0	0	0	1	0	0	1	1	1

해설

dfs를 통해 문제를 풀었다.

 

주의해야할 점은 m, n을 헷갈리지 말아야 한다는 것이다.

m이 가로, n이 세로이므로 이차원 배열을 만들 때 field[n][m]과 같이 되야 한다.

따라서 배추가 있는 위치는 field[n][m] = 1이 된다.

 

배추의 위치를 전부 표기하였다면 연속된 위치에 있는 배추를 조사해야 한다.

(0, 1), (0, -1), (1, 0), (-1, 0) 이렇게 4가지 방향을 조사하면 된다.

 

만약 이동한 위치에 배추가 있다면 이미 조사한 것을 체크해주기 위한 배열을 true로 해준다.

주변에 더 이상의 배추가 없을 때까지 계속해서 조사를 한다.

아직 방문하지 않은 배추가 발견되었다면 애벌레의 수를 1 증가시킨다.

소스 코드

import java.util.*

lateinit var field: Array<IntArray>
lateinit var visit: Array<BooleanArray>
val dx = arrayOf(0, 0, 1, -1)
val dy = arrayOf(1, -1, 0, 0)
var width = 0
var vertical = 0
var k = 0

fun main() = with(System.`in`.bufferedReader()) {
    val testCase = readLine().toInt()
    repeat(testCase) {
        val st = StringTokenizer(readLine())
        width = st.nextToken().toInt()
        vertical = st.nextToken().toInt()
        k = st.nextToken().toInt()
        field = Array(vertical) { IntArray(width) { 0 } }
        visit = Array(vertical) { BooleanArray(width) { false } }
        repeat(k) {
            val (x, y) = readLine().split(" ").map { it.toInt() }
            field[y][x] = 1
        }
        var cnt = 0
        for(i in 0 until vertical) {
            for(j in 0 until width) {
                if(field[i][j] != 0 && !visit[i][j]) {
                    if(dfs(i, j)) cnt++
                }
            }
        }
        println(cnt)
    }
}

fun dfs(y: Int, x: Int): Boolean {
    if(visit[y][x]) return false
    visit[y][x] = true
    repeat(4) { i ->
        val nx = x + dx[i]
        val ny = y + dy[i]
        if(nx >= 0 && ny >= 0 && nx < width && ny < vertical && field[ny][nx] != 0) dfs(ny, nx)
    }
    return true
}