[백준] 16173 (실버5)

점프게임을 이길 수 있을지 없을지 예측하는 문제이다.
쩰리는 정사각형의 격자판에서 놀기 때문에 이는 2차원 배열을 이용하여 세팅할 수 있을 것 같다.
쩰리는 현재 밟고 있는 칸에 쓰여진 수만큼 아래 혹은 오른쪽으로 움직일 수 있다.
쩰리가 이동가능한 모든 경로를 파악해서 끝점에 도달할 수 있을지 없을지를 알아내야 하는 문제이기 때문에, 깊이우선탐색 DFS 알고리즘을 통해 문제를 해결할 수 있을 것 같다.

def main():
    n = int(input())

    graph = []
    visited = []
    for _ in range(n):
        graph.append(list(map(int, input().split())))
        visited.append([False] * n)

    if dfs(0, 0, graph, visited, n):
        print("Hing")


def dfs(x, y, graph, visited, n):
    # 오른쪽, 아래쪽 이동방향
    dx = [0, 1]
    dy = [1, 0]

    if x >= n or x <= -1 or y >= n or y <= -1:
        return 0
    elif visited[x][y]:
        return 0
    elif graph[x][y] == -1:
        print("HaruHaru")
        exit()
    else:
        visited[x][y] = True    # 방문처리 (이외 추가 작업 할 수 있음)
        for i in range(2):      # dfs 할 곳으로 이동
            nx = x + dx[i] * graph[x][y]
            ny = y + dy[i] * graph[x][y]
            dfs(nx, ny, graph, visited, n)
        return True


main()