백준 16173 점프왕 쩰리 (Small) Python3

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

16173번: 점프왕 쩰리 (Small)

 

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ16173.py

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

import sys
def dfs(x, y):
    global ck
    if ck: return
    if x>=N or y>=N: return
    if x==N-1 and y==N-1:
        ck = True
        return
    jump = area[y][x]
    if jump == 0: return
    dfs(x+jump, y)
    dfs(x, y+jump)

N = int(sys.stdin.readline())
area = []
ck = False
for _ in range(N):
    area.append(list(map(int, sys.stdin.readline().split())))
dfs(0, 0)
if ck: print("HaruHaru")
else: print("Hing")

---

풀이 과정

풀이 시간 20분

import sys
def dfs(x, y):
    global ck
    #이미 성공했다면, return
    if ck: return
    #구역을 벗어난 경우, return
    if x>=N or y>=N: return
    #끝점에 도달한 경우, 성공
    if x==N-1 and y==N-1:
        ck = True
        return
    jump = area[y][x]
    #칸에 쓰여있는 수가 0인 경우, 재귀가 무한정 호출되므로 종료시킨다
    if jump == 0: return
    dfs(x+jump, y)
    dfs(x, y+jump)

N = int(sys.stdin.readline())
area = []

#성공-True, 실패-False
ck = False
for _ in range(N):
    area.append(list(map(int, sys.stdin.readline().split())))
    
#시작점 (x, y) = (0, 0)
dfs(0, 0)
if ck: print("HaruHaru")
else: print("Hing")
#시간복잡도 = O(V+E) = O(N+2N) -> O(N), 공간복잡도 = O(N^2)