[백준 16174] 점프왕 쩰리 (Large) (python)

16174번: 점프왕 쩰리 (Large)

---

BFS를 이용하여 풀면 된다. 아래 오른쪽만 가능하다는 점!

처음에 visited 배열을 쓰지 않고 했더니 시간초과가 났다.

 

1. queue에 시작점을 담는다.
2. arr[x][y] 가 0이라면 더이상 움직일 수 없으므로 break
3. arr[x][y] 가 -1이라면 도착이므로 break

 

import sys
from collections import deque
input = sys.stdin.readline
dx = [0, 1]
dy = [1, 0]

N = int(input())
arr = []
for _ in range(N):
    arr.append(list(map(int, input().split())))
flag = False
queue = deque([[0, 0]])
visited = [[False]*N for _ in range(N)]
while queue:
    x, y = queue.popleft()
    if arr[x][y] == 0:
        break
    if arr[x][y] == -1:
        flag = True
        break
    for i in range(2):
        nx = x + arr[x][y]*dx[i]
        ny = y + arr[x][y]*dy[i]
        if 0 <= nx < N and 0 <= ny < N and not visited[nx][ny]:
            queue.append([nx, ny])
            visited[nx][ny] = True

if flag:
    print("HaruHaru")
else:
    print("Hing")