BOJ 16174 점프왕 쩰리(Python 3)

이 문제는 Large와 Small 두 개를 한번에 맞을 수 있는 문제라 매우 좋은 문제다.

BFS를 배우기 전에는 Small문제 가지고 모든 경우의 수를 파이썬에 만들었다가 틀려서 가슴이 아팠던 기억이 난다.

다이나믹으로 풀 수 있다.

점프할 수 있는 곳이 범위를 초과하지 않을 때 점프하기 전의 위치에 있는 값을 더한다.

그리고 n-1,n-1위치일 때는 for문을 종료하고 HaruHaru나 Hing을 출력한다.

아니면 BFS로 풀 수 있는데 그 코드는 문제집 카테고리에 들어가면 BFS / DFS / Dijkstra / Bellman-Ford 라는 글이 있는데, 거기에 BFS 소스 코드가 있습니다.(https://hello70825.tistory.com/86)

BFS 코드를 보고 싶으면 거기 들어가서 확인하면 됩니다.

코드확인

n=int(input())
D=[list(map(int,input().split())) for _ in range(n)]
S=[[0]*n for _ in range(n)]
S[0][0]=1
for i in range(n):
    for j in range(n):
        if i==n-1 and j==n-1:break
        if i+D[i][j]<n:
            S[i+D[i][j]][j]+=S[i][j]
        if j+D[i][j]<n:
            S[i][j+D[i][j]]+=S[i][j]
print(['HaruHaru','Hing'][S[n-1][n-1]==0])