[백준] 26169 (세 번 이내에 사과를 먹자)

#1 알고리즘

그래프 - 깊이 우선 탐색 (DFS, Depth-First Search)

DFS를 이용했다. 한 단계식 정복해가며 차근차근 나아가는 너비 우선 탐색과 달리, 깊이 우선 탐색은 '한 방향으로 갈 때까지 가보기'를 반복한다. 따라서 BFS보단 DFS가 이 문제에 어울린다. 이 문제에서는 최대 3번 이동해야 한다는 제한이 있다. 깊이 우선 탐색 알고리즘을 살짝 고쳐서, 문제에서 제시한 깊이까지만 수행되도록 만들었다.

 

#2 코드 - 코틀린

#2-1 성공한 코드

var yRange = 0..4 // i
var xRange = 0..4 // j
var depthRange = 0..3
val box = Array(5) { Array(5) { -1 } }
val visited = Array(5) { Array(5) { false } }
var r = -1
var c = -1

const val APPLE = 1
const val EMPTY = 0
const val WALL = -1

const val RESULT_CAN_EAT_APPLE_TWO_OR_MORE = 1
const val RESULT_CANT_EAT_APPLE_TWO_OR_MORE = 0

var result = RESULT_CANT_EAT_APPLE_TWO_OR_MORE

fun main() {
    // (1) 입력 받기
    for (y: Int in yRange) {
        val row = readln().split(" ")
        for (x: Int in xRange) {
            box[y][x] = row[x].toInt()
        }
    }
    val rAndC = readln().split(" ")
    r = rAndC[0].toInt()
    c = rAndC[1].toInt()

    // (2) dfs
    dfs(r, c, visited, 0, 0)  // depth를 0-based indexing으로 둔다. 즉, 3이 depth의 최댓값이 된다.

    // (3) 출력
    println(
        if (result == RESULT_CAN_EAT_APPLE_TWO_OR_MORE) {
            RESULT_CAN_EAT_APPLE_TWO_OR_MORE
        } else {
            RESULT_CANT_EAT_APPLE_TWO_OR_MORE
        }
    )

}

fun dfs(y: Int, x: Int, visited: Array<Array<Boolean>>, depth: Int, prevAppleCount: Int) {
    visited[y][x] = true
    val appleCount = if (box[y][x] == APPLE) {
        prevAppleCount + 1
    } else {
        prevAppleCount
    }

    if (2 <= appleCount) {
        result = RESULT_CAN_EAT_APPLE_TWO_OR_MORE
        return
    }

    for (next in getNexts(y, x)) {
        val nextY = next.first
        val nextX = next.second
        val nextDepth = depth + 1

        if (!visited[nextY][nextX] && nextDepth in depthRange) {
            dfs(nextY, nextX, visited, nextDepth, appleCount)
        }
    }
    
    visited[y][x] = false
}

fun getNexts(prevY: Int, prevX: Int): List<Pair<Int, Int>> {
    val candidates = listOf(
        Pair(prevY - 1, prevX),
        Pair(prevY + 1, prevX),
        Pair(prevY, prevX - 1),
        Pair(prevY, prevX + 1),
    )
    val nexts = ArrayList<Pair<Int, Int>>()
    for (candidate in candidates) {
        val candidateY = candidate.first
        val candidateX = candidate.second

        if (candidateY in yRange && candidateX in xRange && box[candidateY][candidateX] != WALL) {
            nexts.add(candidate)
        }
    }

    return nexts
}

실패했던 코드(#2-2)에서 딱 한 줄 visited[y][x] = false 추가한 코드다. 이 코드는 백트래킹 코드다. 백트래킹에 대한 설명은 여기를 참조하자.

 

#2-2 실패했던 코드

var yRange = 0..4 // i
var xRange = 0..4 // j
var depthRange = 0..3
val box = Array(5) { Array(5) { -1 } }
val visited = Array(5) { Array(5) { false } }
var r = -1
var c = -1

const val APPLE = 1
const val EMPTY = 0
const val WALL = -1

const val RESULT_CAN_EAT_APPLE_TWO_OR_MORE = 1
const val RESULT_CANT_EAT_APPLE_TWO_OR_MORE = 0

var result = RESULT_CANT_EAT_APPLE_TWO_OR_MORE

fun main() {
    // (1) 입력 받기
    for (y: Int in yRange) {
        val row = readln().split(" ")
        for (x: Int in xRange) {
            box[y][x] = row[x].toInt()
        }
    }
    val rAndC = readln().split(" ")
    r = rAndC[0].toInt()
    c = rAndC[1].toInt()

    // (2) dfs
    dfs(r, c, visited, 0, 0)  // depth를 0-based indexing으로 둔다. 즉, 3이 depth의 최댓값이 된다.

    // (3) 출력
    println(result)

}

fun dfs(y: Int, x: Int, visited: Array<Array<Boolean>>, depth: Int, prevAppleCount: Int) {
    visited[y][x] = true
    val appleCount = if (box[y][x] == APPLE) {
        prevAppleCount + 1
    } else {
        prevAppleCount
    }

    if (2 <= appleCount) {
        result = RESULT_CAN_EAT_APPLE_TWO_OR_MORE
        return
    }

    for (next in getNexts(y, x)) {
        val nextY = next.first
        val nextX = next.second
        val nextDepth = depth + 1

        if (!visited[nextY][nextX] && nextDepth in depthRange) {
            dfs(nextY, nextX, visited, nextDepth, appleCount)
        }
    }
}

fun getNexts(prevY: Int, prevX: Int): List<Pair<Int, Int>> {
    val candidates = listOf(
        Pair(prevY - 1, prevX),
        Pair(prevY + 1, prevX),
        Pair(prevY, prevX - 1),
        Pair(prevY, prevX + 1),
    )
    val nexts = ArrayList<Pair<Int, Int>>()
    for (candidate in candidates) {
        val candidateY = candidate.first
        val candidateX = candidate.second

        if (candidateY in yRange && candidateX in xRange && box[candidateY][candidateX] != WALL) {
            nexts.add(candidate)
        }
    }

    return nexts
}

실패한 이유는 코드 속 visited를 BFS처럼 다뤘기 때문이다.

 

A는 출발점 B는 도착점들의 모임이다. 검은색 칸은 장애물이다. A는 문제마다 고정된 값(r과 c)이지만 B는 3번 이동할 수 있는 모든 칸들의 모임이다. 위 도식도에서 b'는 그 모임의 한 원소를 나타낸 것이다. 파란색 칸에 주목하라. 파란색 칸은 이동과 동시에 '방문함'으로 처리될 것이다.

 

파란색 칸의 존재 때문에, b''는 영원히 방문할 수 없게 된다. 즉 DFS를 수행할 때는 방문 기록을 '초기화'해야 한다. BFS때는 한 단계 (한 깊이)가 마무리되어야 다음 단계로 넘어가기에 초기화할 일이 없었던 것과 대조적이다 (물론 BFS도 문제의 조건이 어떻게 나오느냐 따라 필요할 수도 있겠지만 말이다).