1103번 게임

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

---

아이디어

BFS로 푼 문제이다.
해당 칸만큼 상하좌우로 움직일 때

if i == 0:
	nx, ny = x + dx[i] - int(board[x][y]) + 1, y + dy[i]
elif i == 1:
	nx, ny = x + dx[i] + int(board[x][y]) - 1, y + dy[i]
elif i == 2:
	nx, ny = x + dx[i] , y + dy[i] - int(board[x][y]) + 1
else:
	nx, ny = x + dx[i], y + dy[i] + int(board[x][y]) - 1

처음에 이런 식으로 상하좌우 경우를 나눠서 짰었다.
하지만

nx, ny = x + dx[i]*int(board[x][y]), y + dy[i]*int(board[x][y])

이렇게 하면 굉장히 간단해진다.

그리고

if visited[nx][ny] < visited[x][y] + 1:
	visited[nx][ny] = visited[x][y] + 1
	queue.append((nx, ny))

이 조건을 추가하지 않고 여러 번 반복하여 이미 커졌던 수를 갱신해서 시간초과가 났다.

---

코드

import sys
from collections import deque
input = sys.stdin.readline

def bfs():
    queue = deque([(0, 0)])
    visited[0][0] = 1
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx, ny = x + dx[i]*int(board[x][y]), y + dy[i]*int(board[x][y])
            if nx < 0 or nx >= N or ny < 0 or ny >= M or board[nx][ny] == 'H':
                continue
            if visited[nx][ny] < visited[x][y]+1:
                visited[nx][ny] = visited[x][y] + 1
                queue.append((nx, ny))
            if visited[nx][ny] > N*M:
                return -1
    return max(map(max, visited))

N, M = map(int, input().split())
board = [list(input().rstrip()) for _ in range(N)]
visited = [[0] * M for _ in range(N)]
dx = [-1, 1, 0, 0] # 상하좌우
dy = [0, 0, -1, 1]

print(bfs())