[백준] 26169 세 번 이내에 사과를 먹자 [Python, 파이썬]

• 문제 : https://www.acmicpc.net/problem/26169
• dfs, 백트레킹

 

Map = [list(map(int, input().split())) for _ in range(5)]
r, c = map(int, input().split()) # 행, 열

visit = [[0] * 5 for _ in range(5)]
visit[r][c] = 1
mx, my = [1, -1, 0, 0], [0, 0, 1, -1]

def dfs(r, c, d, apple):   # 행, 열, 깊이, 사과 갯수
    if d > 3:   # 4번 이동하면 돌아가
        return
    if apple >= 2:  # 사과 2개 먹었으면 나가
        print(1)
        exit()
    
    for i in range(4):  # 상하좌우 네 방향 탐색
        nx, ny = r + mx[i], c + my[i]

        if 0 <= nx < 5 and 0 <= ny < 5 and visit[nx][ny] == 0 and Map[nx][ny] != -1:
            visit[nx][ny] = 1   # 밟은 자리 장애물 설치
            dfs(nx, ny, d+1, apple+Map[nx][ny])
            visit[nx][ny] = 0   # 돌아와서는 장애물 제거
    


dfs(r, c, 0, 0) # 시작 위치 r, c, 이동 횟수 0, 먹은 사과 0 부터 시작
print(0)