‘쩰리’는 점프하는 것을 좋아하는 젤리다. 단순히 점프하는 것에 지루함을 느낀 ‘쩰리’는 새로운 점프 게임을 해보고 싶어 한다. 새로운 점프 게임의 조건은 다음과 같다.
새로운 게임이 맘에 든 ‘쩰리’는, 계속 게임을 진행해 마침내 최종 단계에 도달했다. 하지만, 게임을 진행하는 구역이 너무 넓어져버린 나머지, 이 게임에서 이길 수 있는지 없는지 가늠할 수 없어졌다. ‘쩰리’는 유능한 프로그래머인 당신에게 주어진 구역에서 승리할 수 있는 지 알아봐 달라고 부탁했다. ‘쩰리’를 도와 주어진 게임 구역에서 끝 점(오른쪽 맨 아래 칸)까지 도달할 수 있는지를 알아보자!
입력의 첫 번째 줄에는 게임 구역의 크기 N (2 ≤ N ≤ 64)이 주어진다.
입력의 두 번째 줄부터 마지막 줄까지 게임판의 구역(맵)이 주어진다.
게임판의 승리 지점(오른쪽 맨 아래 칸)에는 -1이 쓰여있고, 나머지 칸에는 0 이상 100 이하의 정수가 쓰여있다.
‘쩰리’가 끝 점에 도달할 수 있으면 “HaruHaru”(인용부호 없이), 도달할 수 없으면 “Hing” (인용부호 없이)을 한 줄에 출력합니다.
3
1 1 10
1 5 1
2 2 -1
HaruHaru
# 쩰리는 맨 왼쪽 위의 칸에서 출발해 (행, 열)로 나타낸 좌표계로,
# (1, 1) -> (2, 1) -> (3, 1) -> (3, 3)으로 이동해 게임에서 승리할 수 있다.
3
2 2 1
2 2 2
1 2 -1
Hing
# 쩰리는 맨 왼쪽 위의 칸에서 출발하더라도
# 절대 게임의 승리 지점인 (3, 3)에 도달할 수 없다.
import sys
from collections import deque
input = sys.stdin.readline
def bfs(x, y):
q = deque([(x, y)])
while q:
x, y = q.popleft()
if (x, y) == (n - 1, n - 1):
return 1
for i in range(2):
nx = x + dx[i] * graph[x][y]
ny = y + dy[i] * graph[x][y]
if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny]:
q.append((nx, ny))
visited[nx][ny] = 1
return 0
n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]
visited = [[0] * n for _ in range(n)]
dx = [0, 1]
dy = [1, 0]
print("HaruHaru" if bfs(0, 0) else "Hing")
쩰리가 오른쪽, 아래쪽으로만 이동할 수 있기 때문에 방향벡터를 두 개 만들어놓고 BFS를 수행한다. 해당 칸에 적힌 숫자만큼만 이동할 수 있고 그 숫자 미만으로 이동할 수는 없기 때문에 조건이 그렇게 까다로운 문제는 아니었다.
다만 visited[nx][ny] = 1 방문처리를 가장 안쪽 if문에서 해주지 않고 큐에서 pop한 뒤에 해주도록 짰더니 시간초과가 났다. 같은 위치를 여러 번 탐색시키지 않도록 주의하자.