[백준] 나이트 투어 (1331)

문제 설명

백준 1331번 문제 링크

입력 및 출력

» 입력

36개의 줄에 나이트가 방문한 순서대로 입력이 주어진다.

» 출력

첫째 줄에 문제의 정답을 출력한다.

예제 입출력(테스트케이스)

입력	출력
A1 B3 A5 C6 E5 F3 D2 F1 E3 F5 D4 B5 A3 B1 C3 A2 C1 E2 F4 E6 C5 A6 B4 D5 F6 E4 D6 C4 B6 A4 B2 D1 F2 D3 E1 C2	Valid

문제 풀이 (KOTLIN)

import kotlin.math.abs

val set = mutableSetOf<String>()
var check = true

fun main(args: Array<String>) = with(System.`in`.bufferedReader()) {
    //처음(현재) 위치
    var current = readLine()

    //마지막 위치에서 처음 시작 위치를 비교하기 위해 처음 값 저장
    val first = current
    set.add(current)

    for (i in 1..35) {
        //현재 위치와 비교하기 위한 다음 위치
        val next = readLine()

        //MutableSet<T> add 함수
        //MutableSet 내부에 원소가 없을 경우, add 후 true(Boolean)을 리턴
        //MutableSet 내부에 원소가 있을 경우, false(Boolean)를 리턴

        //다음으로 이동할 위치를 MutableSet에 넣고 결과값을 확인
        //next가 MutableSet에 있을 경우, "Invalid"
        if (!set.add(next)) {
            check = false
            break

            //next가 MutableSet에 없을 경우
        } else {

            //MutableSet에 next를 추가하고, 나이트의 올바른 이동이 맞는지 체크
            //next가 나이트의 올바른 경우가 아닌 경우 "Invalid"
            if (!isMovedCorrectly(current, next)) {
                check = false
                break
            }
        }

        //next를 다음번 이동 경로와 비교하기 위해 current로 값 이동
        current = next

        //나이트가 마지막 위치까지 성공적으로 도달했을 경우,
        //마지막 위치에서 처음 시작점으로 이동가능한지 체크
        //마지막 위치에서 시작 위치로 이동이 불가능할 경우 "Invalid"
        if (i == 35 && !isMovedCorrectly(first, next)) check = false
    }

    if (check) println("Valid")
    else println("Invalid")
}

//현재 위치와 새로운 위치가 올바른 나이트의 경로인지 체크
//올바른 이동일 경우 true(Boolean), 올바르지 않은 이동일 경우 false(Boolean)
fun isMovedCorrectly(current: String, next: String): Boolean {
    return when {
        //나이트이 이동 경로가 올바른 경우

        //A~Z의 좌표를 2(절대값)칸 이동한 경우, 1~6의 좌표를 1(절대값)만큼 움직여야 함
        abs(current[0] - next[0]) == 2 -> abs(current[1] - next[1]) == 1

        //A~Z의 좌표를 1(절대값)칸 이동한 경우, 1~6의 좌표를 2(절대값)만큼 움직여야 함
        abs(current[0] - next[0]) == 1 -> abs(current[1] - next[1]) == 2

        //A~Z는 반드시 1~2(절대값)만큼 이동해야함,
        //0(제자리) 이거나 3(절대값)이상 이동한 경우는 나이트의 올바른 이동이 아님
        else -> false
    }
}

문제 풀이 (SWIFT)

let pos = [(-2, -1), (-2, 1), (-1, 2), (1, 2), (2, 1), (2, -1), (1, -2), (-1, -2)]
var chess = Array(repeating: Array<Bool>(repeating: false, count: 6), count: 6)
var start: (x: Int, y: Int) = (0, 0)
var prev: (x: Int, y: Int) = (0, 0)
var end: (x: Int, y: Int) = (0, 0)
var tour = true

for count in 0..<36 {
    let axis = Array(readLine()!)
    let x = Int(axis[0].asciiValue!) - 65
    let y = Int(String(axis[1]))! - 1
    
    if count == 0 {
        chess[x][y].toggle()
        start.x = x
        start.y = y
        prev.x = x
        prev.y = y
        continue
    } else {
        if count == 35 {
            end.x = x
            end.y = y
        }
        
        tour = false
        for p in pos {
            let nx = prev.x + p.0
            let ny = prev.y + p.1
            
            if (0..<6).contains(nx) && (0..<6).contains(ny) {
                if nx == x && ny == y && !chess[nx][ny] {
                    chess[nx][ny].toggle()
                    prev.x = nx
                    prev.y = ny
                    tour = true
                    break
                }
            }
        }
        
        if !tour {
            break
        }
    }
    
}

if tour {
    tour = false
    
    for p in pos {
        let nx = end.x + p.0
        let ny = end.y + p.1
        
        if (0..<6).contains(nx) && (0..<6).contains(ny) {
            if nx == start.x && ny == start.y {
                tour = true
                break
            }
        }
    }
}


print(tour ? "Valid" : "Invalid")