백준 1600 말이 되고픈 원숭이

haruponea·2021년 3월 25일
0

BOJ

목록 보기
27/41

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

풀이
문제를 보고 바로 저번에 풀었는 2206번풀이 문제가 기억났다. 이 문제 역시 비슷하게 vis배열을 3차원 배열로 만들면 쉽게 풀 수 있는 문제였다. vis[k][x][y] 는 말처럼 이동을 k번 했을 때 (x, y)위치에 오는데 이동한 횟수이다.

시간초과에 관한 tip을 주자면 아래처럼 함수로 만들면 걸리는 시간이 줄어든다! 전역에 전부 때려박는 습관을 버리고 함수를 자주 만들자. 아래 코드는 통과 되지만 함수 내부를 전역에서 돌리면 TLE가 뜬다.

Python

from collections import deque
import sys
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
dhx = [-2, -2, -1, -1, 1, 1, 2, 2]
dhy = [-1, 1, -2, 2, -2, 2, -1, 1]
k = int(sys.stdin.readline().strip())
m, n = map(int, sys.stdin.readline().split())
board = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
vis = [[[-1]*m for _ in range(n)] for _ in range(k+1)]
def bfs():
    q = deque()
    q.append((0, 0, 0))
    vis[0][0][0] = 0
    while q:
        cnt, x, y = q.popleft()
        if x == n - 1 and y == m - 1:
            print(vis[cnt][x][y])
            sys.exit()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m and board[nx][ny] == 0:
                if vis[cnt][nx][ny] == -1:
                    vis[cnt][nx][ny] = vis[cnt][x][y] + 1
                    q.append((cnt, nx, ny))
        if cnt < k:
            for i in range(8):
                nx = x + dhx[i]
                ny = y + dhy[i]
                if 0 <= nx < n and 0 <= ny < m and board[nx][ny] == 0:
                    if vis[cnt + 1][nx][ny] == -1:
                        vis[cnt + 1][nx][ny] = vis[cnt][x][y] + 1
                        q.append((cnt + 1, nx, ny))
    print(-1)
bfs()

0개의 댓글