[백준_16174]_점프왕젤리(Large)_python

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

16174번: 점프왕 쩰리 (Large)

문제

 ‘쩰리’는 유능한 프로그래머인 당신에게 주어진 구역에서 승리할 수 있는지 알아봐 달라고 부탁했다. ‘쩰리’를 도와 주어진 게임 구역에서 끝 점(오른쪽 맨 아래 칸)까지 도달할 수 있는지를 알아보자!

입력

입력의 첫 번째 줄에는 게임 구역의 크기 N (2 ≤ N ≤ 64)이 주어진다.

입력의 두 번째 줄부터 마지막 줄까지 게임판의 구역(맵)이 주어진다.

게임판의 승리 지점(오른쪽 맨 아래 칸)에는 -1이 쓰여있고, 나머지 칸에는 0 이상 100 이하의 정수가 쓰여있다.

출력

‘쩰리’가 끝 점에 도달할 수 있으면 “HaruHaru”(인용부호 없이), 도달할 수 없으면 “Hing” (인용부호 없이)을 한 줄에 출력합니다.

문제 해결

dfs 기본문제이다.

문제에 쩰리의 이동 범위가 주어지고 graph의 현 위치에 적혀있는 숫자만큼 오른쪽 혹은 아래로 한 방향으로만 이동 가능하다

dx에 쩰리의 이동방향을 나타내고 graph의 현 위치 값을 곱하여 이동하도록 하였다.

그래프의 값이 -1이 되는지의 유무에 따라 출력 조건에 맞춰 출력해주면 된다.

#단방향 오른쪽*n 아래*n
n = int(input())
graph = [list(map(int,input().split())) for _ in range(n)]
visited = [[0]*n for _ in range(n)]
dx,dy = [1,0],[0,1]

def in_range(x,y):
    return 0<=x<n and 0<=y<n

def dfs(x,y):#0,0
    visited[x][y] = True
    for i in range(2):
        nx,ny = x + dx[i]*graph[x][y] , y + dy[i]*graph[x][y]
        if in_range(nx,ny) and not visited[nx][ny]:
            if graph[nx][ny] == -1 :
                print("HaruHaru")
                exit(0)
            else:
                dfs(nx,ny)
    return False

if not dfs(0,0):
    print("Hing")