[백준 1331번] [Kotlin] 나이트 투어

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

1331번: 나이트 투어

 

난이도 : 실버 4
태그 : 구현, 시뮬레이션

 

 

설명

 

6 * 6 체스판 위 한 점에서 시작하여

나이트가 이동하며 모든 칸을 한 번씩만 (두 번 이상 같은 곳을 방문하면 실패) 방문하면서,

첫 시작점으로 돌아올 수 있는지 확인하는 문제입니다.

 

 

해당 문제 매 좌표 입력을 받을 때 마다 체크해야 할 것이 있습니다.

1. 이미 방문했는가(2번 이상 같은 칸을 반복할 수 없음) -> 2차원 boolean - visited 배열로 체크하였습니다

2. 나이트의 이동 방법으로 이동이 가능한 좌표인가

-> 바로 직전 x좌표와의 차이가 2일 경우 y좌표와 직전 y좌표의 차이는 1,

직전의 y좌표와의 차이가 2일 경우 x좌표와의 차이는 1이 되어야함

 

또, 마지막 좌표를 입력받고, 이 좌표에서 첫 좌표로 이동이 가능한지 확인해야 합니다.

 

 

 

소스코드

import kotlin.math.abs
import kotlin.system.exitProcess

fun main() = with(System.`in`.bufferedReader()) {

    val initialInput = readLine()
    val ix = initialInput[0] - 'A'
    val iy = initialInput[1].digitToInt() - 1
    var oldX = ix
    var oldY = iy

    val visited = Array(6) { BooleanArray(6) }
    visited[ix][iy] = true

    repeat(35) {
        val newInput = readLine()
        val nx = newInput[0] - 'A'
        val ny = newInput[1].digitToInt() - 1

        if (visited[nx][ny]) exit()
        visited[nx][ny] = true

        val dx = abs(oldX - nx)
        val dy = abs(oldY - ny)
        if (!(dx == 2 && dy == 1 || dx == 1 && dy == 2)) exit()

		// 직전 값 저장
        oldX = nx
        oldY = ny
    }

    val dx = abs(ix - oldX)
    val dy = abs(iy - oldY)
    if (!(dx == 2 && dy == 1 || dx == 1 && dy == 2) || visited.sumOf { it.count { !it } } > 0) exit()

    println("Valid")
}

fun exit() {
    println("Invalid")
    exitProcess(0)
}