[Swift] 백준 1783 - 병든 나이트

문제 바로가기

풀이

범위를 나워서 풀어야하는 문제이다.
문제를 처음 봤을 땐 체스가 움직이는 네 가지 경우를 제시하기에 bfs로 푸는건가? 싶었는데
이동 횟수가 4번보다 많은 경우 이동 방법을 모두 사용해야한다는 것을 보고 조건별로 푸는 것이구나 했다.

1) N == 1 인 경우

• 나이트는 위로든, 아래로든 움직일 수가 없고 시작 위치만 방문할 수 있다.
• 방문할 수 있는 칸의 수는 1이다.

2) N == 2 인 경우

• 2번(1칸 위로, 2칸 오른쪽) 또는 3번(1칸 아래로, 2칸 오른쪽)으로만 이동이 가능하다. 따라서 최대 4회 이동이 가능하다(4회를 넘으면 1,2,3,4번 모두를 사용해서 이동해야하기 때문에)
• 따라서 방문할 수 있는 칸의 수는 min(4,(M+1)/2)이다.
  • (M+1)/2 인 이유 ?
    • M이 1 또는 2 인 경우 -> 1, 3 또는 4인 경우 -> 2, 5 또는 6인 경우 -> 3, 7 또는 8인 경우 -> 4 이기 때문이다.

3) N >= 3 인 경우

• 1,2,3,4 번 모두 이동이 가능하다.
  • 그러나 1,2,3,4번을 모두 이동하기 위해서는 M이 최소 6이상이여야한다.
• 따라서 만약 M <= 6이라면 방문할 수 있는 칸의 수는 min(4,M)이고 그렇지 않으면 M-2만큼 이동이 가능하다.
  • M-2인 이유? : 1,2,3,4번 모두 이동을 반드시 만족해야하는데, 이를 만족하면 2칸은 이동할 수 없게 되기 때문이다. 그 이후로는 모든 칸으로 이동이 가능하기 때문에 M-2이다.

제출 코드

import Foundation

let input = readLine()!.split(separator:" ").map{Int(String($))!}

let N = input[0]
let M = input[1]

if N == 1 {
	print(1)
} else if N == 2 {
	print(min(4,(M+1)/2))
} else {
	if M <= 6 {
    	print(min(4,M))
    } else {
    	print(M-2)
    }
}