[백준] 21736 (헌내기는 친구가 필요해)

#1 알고리즘

재귀 함수를 이용해 푼다. 그 함수의 시작점은 도연이의 좌표다. 함수의 내용은 아래와 같다.

 

1. 매개변수로 받은 좌표가 캠퍼스 영역을 벗어났거나, 값이 'X'면 함수를 종료한다.
2. 해당 좌표에 새내기가 있다면 '새내기 카운트'를 +1한다.
3. 이제 해당 좌표는 더 볼 일 없으므로 좌푯값에 'X'를 대입한다.
4-1. 현재 좌표에서 한 칸 동쪽 좌표를 인수로 가지는 재귀 호출을 수행한다. 
4-2. 현재 좌표에서 한 칸 서쪽 좌표를 인수로 가지는 재귀 호출을 수행한다.
4-3. 현재 좌표에서 한 칸 남쪽 좌표를 인수로 가지는 재귀 호출을 수행한다.
4-4. 현재 좌표에서 한 칸 북쪽 좌표를 인수로 가지는 재귀 호출을 수행한다.

 

#2 코드 - 코틀린

var n: Int = -1
var m: Int = -1
lateinit var campusMap: Array<Array<Char>>
var locationOfDoyeon = Pair(-1, -1)
var metPeopleCount = 0

fun main() {
    val campusInformation = readln().split(" ")
    n = campusInformation[0].toInt() // 세로 칸 수 (세로의 길이)
    m = campusInformation[1].toInt() // 가로 칸 수 (가로의 길이)
    campusMap = Array(n) { Array(m) { 'O' } } // 알파벳 대문자 'O'으로 초기화 (숫자 0 아님)

    // campusMap 완성
    for (y: Int in 0..<n) { // 세로 순회
        val row = readln()

        for (x: Int in 0..<m) { // 가로 순회
            campusMap[y][x] = row[x]

            if (row[x] == 'I') {
                locationOfDoyeon = Pair(y, x)
            }
        }
    }

    // 재귀함수 호출
    findSaenaegi(locationOfDoyeon.first, locationOfDoyeon.second)

    // 출력
    if (metPeopleCount == 0) {
        println("TT")
    } else {
        println(metPeopleCount)
    }
}

fun findSaenaegi(y: Int, x: Int) {
    if (canGo(y, x)) {
        
        if(campusMap[y][x] == 'P') {
            metPeopleCount++
        }
        
        campusMap[y][x] = 'X' // 이미 지난 위치는 벽으로 취급

        findSaenaegi(y + 1, x) // 북
        findSaenaegi(y - 1, x) // 남
        findSaenaegi(y, x - 1) // 서
        findSaenaegi(y, x + 1) // 동
    }
}

fun canGo(y: Int, x: Int): Boolean {
    // 캠퍼스 영역을 벗어났는지 확인 (y축)
    if (y !in 0..<n) {
        return false
    }

    // 캠퍼스 영역을 벗어났는지 확인 (x축)
    if (x !in 0..<m) {
        return false
    }

    // 'X'인지 확인 (= 벽이거나, 이미 지났던 위치인 지 확인)
    if (campusMap[y][x] == 'X') {
        return false
    }

    return true
}