백준 알고리즘 16173번 점프왕 쩰리 (Small)(python)

기본적인 BFS, DFS 문제이다. (N, N) 좌표에 도착할 수 있는지를 확인해주면 된다.

BFS 풀이

from collections import deque

def bfs(y, x):
    q = deque()
    q.append((y, x, li[y][x]))
    while q:
        y, x, d = q.popleft()
        for i, j in [(1, 0), (0, 1)]:
            Y, X = y + d*i, x+ d*j
            if 0 <= Y < N and 0 <= X < N and d != 0:
                if Y == X == N-1:
                    return True
                q.append((Y, X, li[Y][X]))
    return False
        
N = int(input())
li = [list(map(int, input().split())) for _ in range(N)]    
print("HaruHaru" if bfs(0, 0) else "Hing")

DFS 풀이

import sys
sys.setrecursionlimit(10000)

def dfs(y, x):
    global ok
    d = li[y][x]
    for i, j in [(1, 0), (0, 1)]:
        Y, X = y + d*i, x+ d*j
        if 0 <= Y < N and 0 <= X < N and d != 0:
            if Y == X == N-1:
                ok = 1
                return ;
            dfs(Y, X)
        
N = int(input())
li = [list(map(int, input().split())) for _ in range(N)]
ok = 0
dfs(0, 0)
print("HaruHaru" if ok else "Hing")