[백준 1783번] 병든 나이트 - 파이썬

 

문제 링크:

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

1783번: 병든 나이트

 

 

---

 

풀이 과정:

이 문제는 BFS(너비 우선 탐색)이 아니라 일일이 조건을 설정하여 답을 도출해야 하는 문제이다.

문제만 보면 방문할 수 있는 칸의 개수가 최댓값을 답을 (m-2)로 착각할 수 있다.

그러나 모든 답이 그렇지만은 않다.

세로와 가로의 길이를 설정하여 다음 풀이코드와 같이 풀어야 올바른 답을 도출할 수 있다.

 

풀이 코드:

# 1783번 병든 나이트

n, m = map(int, input().split())
# 세로가 1일 경우 시작지점만 방문 가능
if n == 1:
    print(1)
# 세로가 2일 경우 문제에서 2번, 3번만 이동 가능
elif n == 2:
	# 모든 이동방법을 사용할 수 없기 때문에 (4와 이동 가능한 방법)의 최솟값을 출력
    print(min(4, (m-1)//2+1))
# 가로가 6보다 작거나 같으면 1번, 4번만 이동하는 것이 최댓값
elif m <= 6:
	# 4와 m값 중 작은 값 출력
    print(min(4, m))
# 모든 방법을 쓸 수 있을 때 m-2가 최댓값
else:
    print(m-2)

 

백준 1783번 병든 나이트