백준 알고리즘 - 병든 나이트 (1783) [Python]

 

 

 문제

 

www.acmicpc.net/problem/1783

1783번: 병든 나이트

 

 

 

 

 

 

 문제 상황

 

- 나이트가 이동하며 최대한 많은 지점을 방문할 방법을 고려한다. dfs를 통해 개수를 카운트할 수 있지만 문제의 분류가 탐욕법이고 가로와 세로의 범위가 2,000,000,000 이하이므로 다른 방법을 생각해보아야한다.

 

 

 

 

 

 

 

 해결 전략

 

- 문제의 상황을 일일이 가정하고 범위를 정의해 상황에 맞춰 시뮬레이션한다.

 

 

 

 

 

 

 코드

 

from sys import stdin
input = stdin.readline
N, M = map(int, input().split())
# 4가지 방향을 모두 사용하는 방법은 N>=3(위로 최소 2번 가야하므로), M>=7(오른쪽으로 2씩 2번, 1씩 2번 움직이므로) 이상인 경우이다.
cnt = 1
 
if N==1 or M==1 : cnt =1
elif M >=7: # 가로가 7보다 클 경우
    cnt = (M-6)+4 if N>=3 else 4
    # 4번 이상 이동할 경우 최소 한번씩 방향을 이동해야하므로 오른쪽으로 2씩 2번, 1씩 2번 움직이는 6번의 이동이 필요하다.
    # 가로 6 이상의 체스판은 이동할 경우 시작점 이외에 4개의 포인트를 지나므로 M-6은 시작점과 M이 늘어날 때 생기는 추가점, 4는 기본적으로 움직여야하는 4개의 점이 된다.
    # 세로가 3보다 클 경우 4가지 방향을 모두 사용해야한다.
    # 세로가 3보다 작은 경우 4번 이상 움직일 방법이 없으므로 시작점 + 3개의 포인트인 4개 밖에 방법이 없다.
elif 4<=M<7: # M이 4,5,6 이면 
    # N이 3이상인 경우 무조건 4지점만 지날 수 있고
    # N이 3보다 작으면 M이 4일 때 2지점, 5일 때 3지점, 6일때 3지점을 지날 수 있다.
    cnt = 4 if N>=3 else (M+1)//2
elif 2<=M<4: # M이 2 또는 3이면 
    # N이 3이상의 경우 M이 2인 경우 2지점, 3인 경우 3지점을 방문 할 수 있다. 
    # N이 2인 경우는 1지점, 3인 경우는 2지점을 지날 수 있다.
    cnt = M if N>=3 else M-1
print(cnt)
            
    

 

 

 

 

 

 

 

 

 해설

 

- 코드에 기입

 

 

 

 

 

 

 

 새로 학습한 것 & 실수 

 

- 2차원 배열이라고하면 무조건 DFS, BFS를 떠올리는 경향이 있다. 어떤 것이든 고정관념은 좋지 않다.

 

- N==1 or M==1인 상태를 제외하였다. 코드가 간단한 것은 좋지만 일부러 한 줄을 빼서 오류 상황을 만들 필요는 없다.