[백준/BOJ] - 16174번 python 풀이 - dfs

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

16174번: 점프왕 쩰리 (Large)

---

---

문제의 핵심을 파악하는 것이 중요하다.

출발점은 정사각형의 가장 왼쪽, 가장 위의 칸이라는 점

이동 가능한 방향은 오른쪽과 아래 뿐이라는 점

가장 오른쪽 아래에 도착하면 승리한다는 점

이동할 수 있는 칸은 배열에 적혀있는 칸의 크기라는 점

 

dfs 함수 재귀적 호출을 하며 도착지에 도착했을 경우 "HaruHaru" 출력

실패했을 경우 "Hing" 출력

---

import sys
sys.setrecursionlimit(1000000)

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

def dfs(x,y):
    if x==n-1 and y==n-1: #우측맨아래 좌표
        print("HaruHaru")
        exit(0)
    ok[x][y] = True #방문처리
    dx, dy = (0, arr[x][y]), (arr[x][y], 0) #우측, 아래로만 이동 가능
    for i in range(2):
        rx = x + dx[i]
        ry = y + dy[i]
        if (0<=rx<n) and (0<=ry<n): #넘어가지 않게 범위 설정
            if not ok[rx][ry]: #방문 안했다면 
                dfs(rx,ry) # 재귀 호출


dfs(0,0)
print("Hing") #dfs 함수에서 exit 안했다면 패배이므로 "Hing" 출력