백준 - 1347 미로 만들기(Kotlin)

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

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

 

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

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

문의는 댓글 바람.

 

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

 

[문제 설명]

지나간 장소를 지도료 표시하시오.

[접근 방법]

전체 지도의 크기는 주어진 입력이 n일 때, (2 * n + 1) * (2 * n + 1) = n^2입니다.

제한 사항으로 n은 50보다 작다는 조건이 있으므로 충분히 여유가 있습니다.

 

또한 전체 지도에서 미로의 전체 크기는 이동하는 행과 열의 번호와 관련이 있습니다.

전체 범위에서 저 범위만 출력하면 된다.

 

시간복잡도는 전체지도를 초기화하는 O(n^2)이 될듯합니다.

 

[Kotlin 코드]

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

var maxRow = Int.MIN_VALUE
var maxCol = Int.MIN_VALUE
var minRow = Int.MAX_VALUE
var minCol = Int.MAX_VALUE
val directions = arrayOf(-1 to 0, 0 to 1, 1 to 0, 0 to -1)

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    val n = br.readLine().toInt()
    maxRow = n
    minRow = n
    maxCol = n
    minCol = n


    // 시작점
    var currentPoint = n to n
    // 현재 방향의 인덱스 : 시작 방향은 남쪽이므로 2임.
    var currentDirectionIdx = 2
    // 움직일 방향
    val movements = br.readLine().toCharArray()
    // 미로 방문 여부
    val visited = Array(n * 2 + 1) { BooleanArray(n * 2 + 1)}
    visited[n][n] = true

    for (movement in movements) {
        if (movement == 'R' || movement == 'L') {
            currentDirectionIdx = turnDirection(movement = movement, currentDirectionIdx = currentDirectionIdx)
            continue
        }

        // R이나 L이 아니면 전진이므로 이동함
        currentPoint = currentPoint.first + directions[currentDirectionIdx].first to currentPoint.second + directions[currentDirectionIdx].second
        visited[currentPoint.first][currentPoint.second] = true
        maxRow = currentPoint.first.coerceAtLeast(maxRow)
        minRow = currentPoint.first.coerceAtMost(minRow)
        maxCol = currentPoint.second.coerceAtLeast(maxCol)
        minCol = currentPoint.second.coerceAtMost(minCol)
    }


    for (r in minRow..maxRow) {
        for (c in minCol..maxCol) {
            if (visited[r][c]) {
                bw.write(".")
            } else {
                bw.write("#")
            }
        }
        bw.write("\n")
    }
    bw.flush()
}

fun turnDirection(movement: Char, currentDirectionIdx: Int): Int {
    var nextDirectionIdx = currentDirectionIdx
    if (movement == 'R') {
        nextDirectionIdx++
    } else if (movement == 'L') {
        nextDirectionIdx--
    }

    if (nextDirectionIdx > 3) {
        nextDirectionIdx = 0
    } else if (nextDirectionIdx < 0) {
        nextDirectionIdx = 3
    }
    return nextDirectionIdx
}