[ 그리디 ] 백준 1783 병든 나이트

백준 알고리즘 문제 원본

1783번: 병든 나이트

 
방문할 수 있는 칸의 최대 개수를 구하는 문제는 조건에 따라 다양한 접근 방식이 필요하다. 이번 문제해결의 핵심은 체스판의 크기와 나이트의 이동 규칙을 분석하는 것이었다.

---

문제 이해

백준 1783 병든 나이트 문제

 
병든 나이트는 4가지 방법으로만 이동할 수 있다.

1. 2칸 위로, 1칸 오른쪽
2. 1칸 위로, 2칸 오른쪽
3. 1칸 아래로, 2칸 오른쪽
4. 2칸 아래로, 1칸 오른쪽

이동 횟수가 4번 이상일 경우, 4가지 이동 방법을 모두 사용해야 한다. 이러한 제약 아래에서 나이트가 체스판에서 방문할 수 있는 최대 칸 수를 찾아야 한다.

해결 전략

문제 해결을 위해 핵심은, 체스판의 크기와 이동 규칙의 관계를 이해해야한다는 것이다.

기본 제약 조건 확인

체스판의 세로 길이 N과 가로 길이 M에 따라 다르게 접근해야 한다.
나이트의 이동 방법은 세로로 2칸 또는 1칸 이동 후, 가로로 1칸 또는 2칸 이동 할수 있다.
 

1. 세로 길이 N이 1인 경우

나이트는 아무 곳도 이동할 수 없다. 따라서 방문할 수 있는 칸의 최대 개수는 1 이다.
 

1. 세로 길이 N이 2인 경우

나이트는 오직 가로로 2칸 이동하는 방법 2와 3만 사용할 수 있다.
이 경우, 최대 방문 가능한 칸의 수는 min((M−1)/2+1,4)가 된다. 여기서 M−1을 2로 나눈 후 1을 더하는 이유는 첫 위치를 포함하여 계산하기 위함이고, 최대 4칸을 방문할 수 있다.(4칸 이상 방문을 하기위해선 모든 방법을 사용해야한다. 이 경우에서는 모든 방법을 사용하지 않는 경우를 다룬다.)
 

1. 세로 길이 N이 3 이상이고 가로 길이 M이 7 미만인 경우

이 경우 나이트는 모든 이동 방법을 사용할 수 있지만, 가로 길이 제한으로 인해 최대 4칸만 방문할 수 있다.
 

1. 세로 길이 N이 3 이상이고 가로 길이 M이 7 이상인 경우

나이트는 모든 이동 방법을 사용할 수 있으며, 제한 없이 가로로 이동할 수 있다.
첫 4칸을 방문한 이후, 나이트는 매 이동마다 새로운 칸을 방문할 수 있으므로, 최대 방문 가능한 칸의 수는 M−2가 된다.

 

요약
1. N=1: 나이트는 움직일 수 없으므로, 방문할 수 있는 칸의 최대 개수는 1 이다.
2. N=2: 나이트는 가로로 2칸 이동하는 방법 2와 3만 사용할 수 있다. 최대 방문 가능한 칸의 수는 min((M−1)/2+1,4) 가 된다.
3.N≥3 및 M<7: 가로 길이 M이 작아 나이트의 이동이 제한되므로, 최대 4칸만 방문할 수 있다.
4. N≥3 및 M≥7: 나이트는 제한 없이 가로로 이동할 수 있으며, 최대 방문 가능한 칸의 수는 M−2가 된다.

 

Kotlin 코드 구현

fun main() { 
    val (n, m) = readLine()!!.split(" ").map { it.toInt() } 
    val maxVisits = when {
        n == 1 -> 1 
        n == 2 -> minOf((m - 1) / 2 + 1, 4)
        m < 7 -> minOf(m, 4) 
        else -> m - 2 } 

    println(maxVisits) 
}

---

결론

병든 나이트의 체스판 문제는 체스판의 크기와 이동 규칙을 이해하고, 이에 따른 최적의 전략을 적용한다면 해결할 수 있었다. 이를 위해서는 분기 조건에 대한 파악이 필수적 이었으나, 나는 분기 조건에 대한 이해가 부족했다. 그래서 다른 풀이를 참고하여 해당 문제를 풀이했다.
 
다른 문제풀이를 참고하면서, 분기조건에 대한 생각과 풀이가 신기했다. 특히 n, m 의 값에 따라 달라지는 조건에 대하여, 함께 다루는게 아닌, 앞단에서 하나의 값만으로 해당 조건을 처리하는 조건이 가장 인상적이었다. 
 
특히 복잡한 문제를 해결할 때 다양한 조건을 어떻게 효율적으로 처리할지 고민하는 과정은 문제 해결 능력와 관련하여, 내가 여전히 아직 많이 부족하다는 것을 인정하며, 코딩 피지컬을 열심히 키워야겠다.