[BOJ] 20169 세 번 이내에 사과를 먹자 Python

import pprint
graph = []
visited = [[False for _ in range(5)] for __ in range(5)]
flag = False
for i in range(5):
    graph.append(list(map(int, input().split())))

n, m = map(int, input().split())

def BFS(x, y, apple, depth = 0):
    global flag
    visited[x][y] = True
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    if (depth <= 3 and apple >= 2):
        flag = True
        return
    
    if (depth >= 3 and apple < 2):
        return
    
    for i in range(4):

        xx = dx[i] + x
        yy = dy[i] + y
        if 0 <= xx < 5 and 0 <= yy < 5:
            if graph[xx][yy] == 0 and visited[xx][yy] == False:
                BFS(xx, yy, apple, depth + 1)
        
            elif graph[xx][yy] == 1 and visited[xx][yy] == False:
                BFS(xx, yy, apple + 1, depth + 1)
            
            else:
                continue
        
            visited[xx][yy] = False
    
    if depth == 0:
        if flag:
            return 1
        return 0

    

print(int(BFS(n, m, 0)))

단순 BFS로 문제를 풀이하려 했는데 몇몇 케이스에서 반례가 발생함.

나머지는 BFS와 동일하므로 아래 for문만 자세한 설명 첨부함.

 

    for i in range(4):

        xx = dx[i] + x
        yy = dy[i] + y
        if 0 <= xx < 5 and 0 <= yy < 5:
            if graph[xx][yy] == 0 and visited[xx][yy] == False:
                BFS(xx, yy, apple, depth + 1)
        
            elif graph[xx][yy] == 1 and visited[xx][yy] == False:
                BFS(xx, yy, apple + 1, depth + 1)
            
            else:
                continue
        
            visited[xx][yy] = False

xx, yy의 범위가 graph를 벗어나지 않는경우.

1. 이동한 지점이 길인 경우 (0인 경우) => 깊이만 증가시켜 재귀

2. 이동한 지점이 사과인 경우 (1인 경우) => 깊이와 apple을 증가시켜 재귀

3. 장애물인 경우 => pass

이후 이동한 지점을 False로 바꿔주면서 백트래킹 -> 이부분 추가 안해서 반례가 자꾸 생김