[백준 16173] 점프왕 쩰리 - 파이썬

문제

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

16173번: 점프왕 쩰리 (Small)

 

 

 

풀이 방법

시작 지점인 (0, 0)부터 시작하여 dfs로 돌면서 방문한 곳은 visited 배열에서 1로 바꿔준다.

좌표가 맵 밖을 벗어나거나 이미 방문한 곳은 return으로 빠져나온다. 

도착 지점에 도착했으면 (= visited 배열에서 도착 지점에 해당하는 곳이 1이면) 성공한 것으로 간주한다.

 

 

 

코드

n = int(input())
board = [list(map(int, input().split())) for _ in range(n)]
visited = [[0]*n for _ in range(n)]

def dfs(x, y):
    if x < 0 or x >= n or y < 0 or y >= n or visited[x][y] == 1:
        return
    
    if board[x][y] == -1:
        visited[x][y] = 1
        return
    
    visited[x][y] = 1
    
    dfs(x + board[x][y], y)
    dfs(x, y + board[x][y])
    
    
dfs(0, 0)
if visited[-1][-1] == 1:
    print('HaruHaru')
else:
    print('Hing')