백준 - 감시 피하기(Kotlin)

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.

https://github.com/ROUTINE-STUDY/Algorithm

 

저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문의는 댓글 바람.

 

문제 출처 :https://www.acmicpc.net/problem/18428

 

[접근 방법]

1.완전탐색으로 지도에서 무작위로 3곳에 장애물을 세운다. N^2C3 -> O(N^6)

2.선생님의 4방향에 학생이 있나 체크한다. T(선생님의 수) -> O(4T)

-> O(N^3*T)

 

import java.io.BufferedReader
import java.io.InputStreamReader

lateinit var map: Array<CharArray>
var N = 0
lateinit var teacherPosition: ArrayList<IntArray>
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    N = readLine().toInt()
    map = Array(N){CharArray(N)}
    teacherPosition = ArrayList<IntArray>()
    repeat(N) {
        readLine().split(" ").forEachIndexed { index, s ->
            map[it][index] = s[0]
            if (s[0] == 'T') {
                teacherPosition.add(intArrayOf(it,index))
            }
        }
    }

    if (placeObstacle(map, 0)) {
        println("YES")
    } else {
        println("NO")
    }
}

fun placeObstacle(map: Array<CharArray>, cntOfPlacedObstacle: Int): Boolean {
    if (cntOfPlacedObstacle == 3) {
        if (checkDirection(teacherPosition)) {
            return true
        }
        return false
    }

    for (row in 0 until N) {
        for (column in 0 until N) {
            if (map[row][column] == 'X') {
                map[row][column] = 'O'
                if (placeObstacle(map, cntOfPlacedObstacle+1)) return true
                map[row][column] = 'X'
            }
        }
    }
    return false
}

fun checkDirection(teacherPosition: ArrayList<IntArray>): Boolean {
    teacherPosition.forEach { position ->
        var currentPosition = arrayOf(position[0],position[1])
        while (0 <= --currentPosition[0]) {
            if (map[currentPosition[0]][currentPosition[1]] == 'S') {
                return false
            } else if (map[currentPosition[0]][currentPosition[1]] == 'O') {
                break;
            }
        }
        currentPosition = arrayOf(position[0],position[1])
        while (++currentPosition[0] < N) {
            if (map[currentPosition[0]][currentPosition[1]] == 'S') {
                return false
            } else if (map[currentPosition[0]][currentPosition[1]] == 'O') {
                break;
            }
        }
        currentPosition = arrayOf(position[0],position[1])
        while (0 <= --currentPosition[1]) {
            if (map[currentPosition[0]][currentPosition[1]] == 'S') {
                return false
            } else if (map[currentPosition[0]][currentPosition[1]] == 'O') {
                break;
            }
        }
        currentPosition = arrayOf(position[0],position[1])
        while (++currentPosition[1] < N) {
            if (map[currentPosition[0]][currentPosition[1]] == 'S') {
                return false
            } else if (map[currentPosition[0]][currentPosition[1]] == 'O') {
                break;
            }
        }
    }

    return true
}

처음으로 시간을 재면서 푼 문제였는데 1시간 좀 안되게 걸렸다.

범위를 대충 신경 쓰고 넘어간 부분에서 실수가 있었다.

배열의 범위는 처음 할 때, 꼼꼼히 보고 넘어가야겠다.