[Python 3] BOJ - 1600 "말이 되고픈 원숭이"

 # 문제 링크 : https://www.acmicpc.net/problem/1600

1600번: 말이 되고픈 원숭이

 # 풀이 :

 개인적으로 이 문제는 벽 부수고 이동하기와 매우 유사하게 풀 수 있다고 생각한다. 따라서, 이 문제의 핵심은 정점 나누기라고 생각한다. 전체 맵으로 보면 같은 위치지만 상태변화에 따라 해당 정점이 다른 의미를 지니기에 상태의 정보를 담을 공간을 추가적으로 만들어 줘야 한다.

 또 주의해야 할 점은 말처럼 이동하는 것을 '특수 이동'이라고 할 때, 반드시 K번째 특수 이동이 최소값을 보장하지 않는 다는 점이다.

<그림 1. 문제 TC에서의 반례>

 문제의 예시 TC를 통해 반례를 들 수 있는데, 문제에서는 K가 1이라서 그때는 K가 1일 때가 최소값이지만, 실제로 K가 제한 없이 사용가능하다고 가정하면 K가 2일 때 2번만에 도착점에 도착할 수 있다. 그런데, K가 3이면 분명히 도착점이 아닌 다른 곳으로 특수 이동을 한 후 도착점에 도착하므로 K가 2일 때보다 동작 횟수가 클 수 밖에 없다. 따라서 반드시 K를 많이 쓴다고 하여, 즉 특수 이동을 많이 쓴다고 그때의 도착 결과가 최소 동작 횟수를 보장하지 않는다는 점이다. 

 따라서 일반적인 동서남북의 4방향으로 탐색 한 후, 큐에 넣어주고 현재 특수 이동을 한 횟수가 K보다 작다면 특수 이동의 방향처럼 이동해주면 된다. 또한 일반적인 BFS처럼 해당 정점을 방문했는지 안했는지를 검사하는 배열이 필요한데, 해당 정점은 총 K개의 특수 이동을 고려해야 하므로 3차원 검사 배열이 필요하다. 따라서 만일 현재 특수 이동 횟수에 따라 중복 검사를 해주면서 가장 먼저 도착점에 도착하는 경우가 최소 경우이므로 정답을 출력하면 된다. 만일 큐가 비게 된다면 이것은 불가능한 경우이므로 -1을 출력하면 된다

 

 # 코드

import sys, collections

# 입력부
k = int(sys.stdin.readline())
m , n = map(int, sys.stdin.readline().split())
table = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

# dx, dy : 일반적인 동서남북 4방향
dx = [0,0,1,-1]
dy = [1,-1,0,0]

# hx, hy : 특수 이동인 8방향
hx = [-1,-2,-1,-2,1,2,1,2]
hy = [-2,-1,2,1,-2,-1,2,1]

# check : 3차원 검사 배열
check = [[[False] * (k + 1) for _ in range(m)] for _ in range(n)]

# go : (a,b)에서 시작하여 특수이동, 일반이동을 모두 고려했을 때 도착점으로 가기 위한 최소 동작 횟수를 리턴하는 함수
def go(a,b):
    q = collections.deque()
    q.append((a,b,0,0))
    # 처음에는 특수 이동을 쓰지 않았으므로 [a][b][0]이다
    check[a][b][0] = True
    while q:
        # x, y : 현재 x좌표, y좌표
        # skill : 현재 특수 이동을 한 횟수
        # cnt : 그때의 동작 횟수
        x,y,skill, cnt = q.popleft()
        
        # 도착점이면 동작 횟수 리턴
        if x == n - 1 and y == m - 1:
            return cnt
            
        # 일반적인 4방향 탐색
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if check[nx][ny][skill] == False:
                    if table[nx][ny] == 0:
                        check[nx][ny][skill] = True
                        # 특수 이동을 쓰지 않았으므로 skill은 증가시키지 않고 큐에 넣는다
                        q.append((nx, ny, skill, cnt + 1))

        # 특수 이동이 가능한 경우
        if skill < k:
            # 특수 이동 8방향 탐색
            for i in range(8):
                nx, ny = x + hx[i], y + hy[i]
                if 0 <= nx < n and 0 <= ny < m:
                    # 현재 특수 이동을 하게 되면 가려는 정점은
                    # 현재 특수 이동 횟수 + 1번째에 방문하는 것이므로
                    # check[nx][ny][skill]이 아니라
                    # check[nx][ny][skill + 1]을 체크해야 한다
                    if check[nx][ny][skill + 1] == False:
                        if table[nx][ny] == 0:
                            check[nx][ny][skill + 1] = True
                            # 다음 이동을 위해 특수 이동을 한번 썼기 때문에 skill을 1증가 시키고 큐에 넣는다
                            q.append((nx,ny,skill+1,cnt + 1))
    
    # 불가능한 경우 -1 리턴
    return -1

# 정답 출력
print(go(0,0))