우주의 IT 소행성

from collections import deque
n = int(input())
matrix = [(list(map(int, input().split()))) for _ in range(n)]
visited = [[False] * n for _ in range(n)]

queue = deque()
queue.append((0, 0))

while queue:
    x, y = queue.popleft()
    visited[x][y] = True
    jump_size = matrix[x][y]
    dx = [0, jump_size]
    dy = [jump_size, 0]

    for i in range(2):
        nx = dx[i] + x
        ny = dy[i] + y

        if n <= nx or n <= ny:
            continue
        if jump_size == 0:
            continue
        if jump_size == -1:
            print("HaruHaru")
            exit(0)
        if not visited[nx][ny]:
            queue.append((nx, ny))
            visited[nx][ny] = True

print("Hing")

https://universe-lee.tistory.com/34

점프왕 쩰리 (small)의 다음편 large이다. 주어진 맵의 크기가 2에서 64로 올라가는데,

이를 메모리나 시간 초과 없이 푸는게 관건이다.

따라서 bfs시에 이미 갔던 길을 계속해서 가게 된다면 결국 도착 하기 전에 시간초과나 메모리 낭비가 생길것이니

이미 갔던 길을 표시하여, 아 여기는 안 갈래! 하면 되는것이다.

visited 라는 리스트를 만들고, bfs시마다 현재 좌표에 일종의 flag를 꽂는다 (방문, 미방문)

나중에 queue에 새로운 위치를 넣을 때 이미 방문한 위치라면 (visited == True) 재 방문하지 않는다.,

from collections import deque
n = int(input())
matrix = [(list(map(int, input().split()))) for _ in range(n)]
visited = [[False] * n for _ in range(n)]

queue = deque()
queue.append((0, 0))

while queue:
    x, y = queue.popleft()
    visited[x][y] = True
    jump_size = matrix[x][y]
    dx = [0, jump_size]
    dy = [jump_size, 0]

    for i in range(2):
        nx = dx[i] + x
        ny = dy[i] + y

        if n <= nx or n <= ny:
            continue
        if jump_size == 0:
            continue
        if jump_size == -1:
            print("HaruHaru")
            exit(0)
        if not visited[nx][ny]:
            queue.append((nx, ny))
            visited[nx][ny] = True

print("Hing")