백준 1600 (말이 되고픈 원숭이)
백준 1600 (말이 되고픈 원숭이)
문제 링크
문제 링크 : https://www.acmicpc.net/problem/1600
문제 접근
말이 되고자 하는 원숭이가 있습니다. 말은 체스에서 나이트라고 생각할 수 있습니다. 하지만 능력이 부족하기에, K번까지만 말을 모방할 수 있습니다. K번 모방한 이후에는, 그냥 상하좌우 1칸씩으로만 움직일 수 있습니다. 격자점에는 장애물이 존재하고, 이를 밟을 수 없습니다. 격자점의 왼쪽 상단에서부터 시작해서, 격자점의 오른쪽 하단까지 가는데 필요한 최소 몇 번 움직여야 하는지 구하는 문제입니다.
격자점을 2차원 배열으로 생각할 수 있습니다. 시작점과 끝점이 주어졌고, 움직이는 방법도 주어졌으므로, bidirection search도 생각해볼 법 하지만 이는 아닌 것 같습니다.
직관적인, state space tree(상태공간 트리)를 만들어보겠습니다.
총 하나의 상태에 대해, 12가지의 다음 상태가 존재함을 알수가 있습니다. 순서가 뒤죽박죽이긴 한데, 앞 4개가 일반 원숭이로 움직이는 것이고, 뒤 8개가 말을 모방해서 움직인다고 나타낸 것 입니다.
마땅한 방법이 딱히 떠오르지 않으므로, 완전 탐색을 해야할 것 같습니다. BFS를 선택하였습니다.
DFS와 BFS
dfs로 풀면 안될까? 라는 생각이 들 수 있습니다. 이 문제는 사실 최단 경로를 구하는 문제로 치환할 수 있는데, 모든 node를 다 탐색하는 dfs와 달리, bfs는 모든 node를 탐색하지 않아도 최단 경로를 구할 수 있습니다. 이유는 간단합니다. 최단 경로는 tree에서 depth가 제일 작은 state임이 자명합니다. bfs는 breadth(폭)을 우선적으로 탐색하기에, 제일 먼저 정답을 찾은 state의 depth가 제일 작을 것이고, 이는 모든 node를 탐색하지 않아도 최단 경로를 구할 수 있음을 나타냅니다. dfs로 풀어도 되긴 하겠네요. 하지만 시간이 좀 더 걸릴 것 같습니다.
dynamic programming
탐색을 할 때는 항상 무한루프 문제를 신경써주어야 합니다. 즉, 내가 방문한 곳은 다시 방문하지 않겠다고 명시적으로 나타내주어야 무한루프 문제가 해결됩니다. 하지만 이 문제는 약간 다릅니다. 왜냐하면 어떤 state에 대해서 단순히 내가 방문했다고 다시 방문하지 않으면 이는 최적의 해를 구할 수 없기 때문입니다. 그림으로 나타내보았습니다. (0,3)에서 (1,5)로 능력을 사용해서 갔습니다. 이제 남은 모방 횟수는 0번입니다. 총 4번 이동했습니다. 하지만 이 경우는 해를 구할 수 없습니다. 왜냐하면 마지막 모방 능력은 destination 바로 전에서 사용해야 하기 때문입니다. 따라서 방문한 위치가 같더라도, 남은 모방 횟수에 따라서 결국 다른 state로 봐야 하는 것입니다. 즉 state는 위치(좌표) 2개, 남은 모방 횟수 1개에 영향을 받는다는 의미입니다. 즉 3개의 parameter에 대해서 state를 생성한다고 볼 수 있습니다.
3개의 parameter에 대해 영향을 받음을 알았으므로, visited 배열의 index를 [pos_x][pos_y][남은 모방 횟수]로 나타내는 3차원 배열을 선언해줍니다. 각 index의 값은 동작 수를 저장한다고 볼 수 있습니다.
이를 염두에 두고, queue를 사용해서 DFS를 구현하였습니다.
소스 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import sys,math
from collections import deque
k=(int)(input())
w,h=map(int,sys.stdin.readline().split())
table=[0 for _ in range(h)]
for i in range(h):
table[i] = list(map(int,sys.stdin.readline().split()))
dx=[-1,0,1,0]
dy=[0,1,0,-1]
horse_dx=[-2,-1,1,2,2,1,-1,-2]
horse_dy=[1,2,2,1,-1,-2,-2,-1]
queue=deque()
queue.append([0,0,k]) #pos_x,pos_y,remain_count, remain_count
visited = [[[math.inf]*(k+1) for _ in range(w)] for _ in range(h)]
visited[0][0][k]=0
while queue :
top=queue.popleft()
pos_x=top[0]
pos_y=top[1]
remain_count=top[2]
if table[pos_x][pos_y]==1 : #장애물
continue
else :
if pos_x==h-1 and pos_y==w-1 :
print(visited[pos_x][pos_y][remain_count])
sys.exit()
for i in range(4) :
if (pos_x+dx[i]>=0 and pos_x+dx[i]<h) and (pos_y+dy[i]>=0 and pos_y+dy[i]<w) :
if visited[pos_x+dx[i]][pos_y+dy[i]][remain_count] > visited[pos_x][pos_y][remain_count]+1 :
queue.append([pos_x+dx[i], pos_y+dy[i], remain_count])
visited[pos_x+dx[i]][pos_y+dy[i]][remain_count]=visited[pos_x][pos_y][remain_count]+1
if remain_count>0 :
for i in range(8) :
if (pos_x+horse_dx[i]>=0 and pos_x+horse_dx[i]<h) and (pos_y+horse_dy[i]>=0 and pos_y+horse_dy[i]<w) :
if visited[pos_x+horse_dx[i]][pos_y+horse_dy[i]][remain_count-1] > visited[pos_x][pos_y][remain_count]+1 :
queue.append([pos_x+horse_dx[i], pos_y+horse_dy[i], remain_count-1])
visited[pos_x+horse_dx[i]][pos_y+horse_dy[i]][remain_count-1]=visited[pos_x][pos_y][remain_count]+1
print(-1)
요약하자면 1) 현재 위치가 장애물이 없다면 계속 탐색을 합니다. 2) 내가 갈 수 있는 12가지의 state에 대해 indexerror를 발생시키지 않는 다음 state에 대해 queue에 넣고 값을 채웁니다. 3) 제일 처음으로 도착지에 방문한 state가 정답일 것입니다. 왜냐하면 탐색 방식을 너비 우선으로 했기 때문입니다.
마무리하며
벌써 1월이 절반이 지났습니다. 요즘 뭐 실패와 같은 이런저런 일이 있어서 싱숭생숭했는데 얼른 정신을 차려야겠습니다.