[백준] 1600 말이 되고픈 원숭이

---

원숭이가 (0, 0) 지점에서 (W-1, H-1)까지 이동하는 이동 횟수의 최소값을 구하는 문제이다.

 

처음 문제를 접하고 DP를 사용하면 해결 할 수 있을 것 같아 시도하였지만, 해결하지 못했다. 다른 풀이를 보니 BFS로 해결할 수 있었다. 

 

먼저 DP로 왜 해결할 수 없었는 지에 대해서 설명한다.

 

입력

1
6 6
0 1 1 1 1 0
0 1 1 1 1 0
0 0 0 0 0 0
1 0 0 0 0 0
1 0 0 0 0 1
1 0 0 0 1 0

출력(정상)
8

위 값이 입력으로 주어져 DFS & DP 를 수행하면 중간 지점에 아래와 같은 결과가 출력된다.

[0, 0, 0, 0, 0, 11]
[1, 0, 0, 0, 0, 10]
[2, 3, 8, 9, 8, 9]
[0, 4, 7, 8, 9, 10]
[0, 5, 6, 7, 8, 0]
[0, 6, 7, 8, 0, 10]

DP[6][6]의 값은 반드시 DP[4][5] 또는 DP[5][4]을 통해 갱신되어야 한다. 현재 DP[6][6]의 값은 DP[4][5]의 값으로 인해 갱신 되었다. 이때 DP[5][4]의 값을 보면 7로 갱신 되어 있기 때문에 다음에 DP[6][6]의 값이 8로 갱신 되어야 할 것 같다.

 

하지만 DP[5][4]의 값은 다시 DP[5][3] 또는 DP[6][2]의 값을 통해 갱신 되었을 것 인데, 만약 DP[6][2]의 값을 통해 갱신되었다면 이미 말과 같은 위치 이동을 한번 사용했기 때문에 DP[6][6]은 8로 갱신될 수 없다.

 

그리고 DP[5][3] + 1 = 7이기 때문에 DP[5][4]가 다시 갱신될 수 없어 DP[6][6]은 10을 값으로 가지게 된다.

 

이를 해결하기 위해 >= 비교를 할 수 도 있지만, 너무나 많은 연산을 요구하기 때문에 시간초과가 발생한다.

 

 

 

BFS를 통해 해결하기 위해서는 (r, c, k) 값에 따른 3차원 배열을 통해 해결할 수 있다.

 

Python

 

	from sys import stdin
	from collections import deque
	readline = stdin.readline
	K = int(readline())
	W, H = map(int, readline().split())
	_map = [list(map(int, readline().split())) for _ in range(H)]
	dr, dc = (1, -1, 0, 0), (0, 0, 1, -1)
	hr, hc = (-1, -2, -2, -1, 1, 2, 2, 1), (-2, -1, 1, 2, -2, -1, 1, 2)
	visited = [[[0 for _ in range(K+1)] for _ in range(W)] for _ in range(H)]
	def solve():
	q = deque()
	q.append((0, 0, K))
	while q:
	r, c, k = q.popleft()
	if r == H-1 and c == W-1:
	return visited[r][c][k]
	# 인접 지역 이동
	for i in range(4):
	nr, nc = r+dr[i], c+dc[i]
	if 0<=nr<H and 0<=nc<W and _map[nr][nc] != 1 and visited[nr][nc][k] == 0:
	visited[nr][nc][k] = visited[r][c][k] + 1
	q.append((nr, nc, k))
	# 말 이동
	if k > 0:
	for i in range(8):
	nr, nc = r+hr[i], c+hc[i]
	if 0<=nr<H and 0<=nc<W and _map[nr][nc] != 1 and visited[nr][nc][k-1] == 0:
	visited[nr][nc][k-1] = visited[r][c][k] + 1
	q.append((nr, nc, k-1))
	return -1
	print(solve())

view raw BOJ1600.py hosted with ❤ by GitHub