[백준] 26170 사과 빨리 먹기 [Python, 파이썬]

• 문제 : https://www.acmicpc.net/problem/26170
• 🔑 DFS, 백트래킹
  • 사과가 있는 위치면 사과 개수를 더해서 다음 칸으로 이동
  • 사과가 없는 위치면 그냥 이동
  • 사과 세 개를 먹으면 짧은 거리로 업데이트
  • 세 개를 못 먹는 경우 -1 출력

 

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 = [0, 0, 1, -1], [1, -1, 0, 0]
answer = 100

def dfs(r, c, d, apple):
    global answer

    if apple == 3:
        answer = min(answer, d)
        return
    
    for i in range(4):
        nx, ny = r + mx[i], c + my[i]

        if 0 <= nx < 5 and 0 <= ny < 5 and MAP[nx][ny] != -1 and visit[nx][ny] == 0:
            if MAP[nx][ny] == 1:
                visit[nx][ny] = 1
                dfs(nx, ny, d+1, apple+1)
                visit[nx][ny] = 0
            else:
                visit[nx][ny] = 1
                dfs(nx, ny, d+1, apple)
                visit[nx][ny] = 0

dfs(r, c, 0, 0)

if answer == 100:
    print(-1)
else:
    print(answer)