728x90
https://www.acmicpc.net/problem/16174
문제의 핵심을 파악하는 것이 중요하다.
출발점은 정사각형의 가장 왼쪽, 가장 위의 칸이라는 점
이동 가능한 방향은 오른쪽과 아래 뿐이라는 점
가장 오른쪽 아래에 도착하면 승리한다는 점
이동할 수 있는 칸은 배열에 적혀있는 칸의 크기라는 점
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" 출력
728x90
'백준 풀이' 카테고리의 다른 글
[백준/BOJ] - 1240번 python 풀이 - bfs (0) | 2023.04.04 |
---|---|
[백준/BOJ] - 6118번 python 풀이 - bfs (0) | 2023.04.03 |
[백준/BOJ] - 15900번 python 풀이 - dfs (0) | 2023.04.02 |
[백준/BOJ] - 13265번 python 풀이 - bfs (0) | 2023.03.27 |
[백준/BOJ] - 5014번 python 풀이 - bfs (0) | 2023.03.27 |