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

https://www.acmicpc.net/problem/26169

 

❗풀이방법

1. 세 번 이하의 이동 -> 시작점 포함 총 4개의 노드에 방문 가능 -> dep의 최대가 4로 설정
2. 그래프를 수정 가능한 것과 원본 그래프 2개로 나누어 원상복구에 사용
3. 총 4개의 정점을 방문했을 때, 시작점이 r, c인지, 경로에 몇 개의 사과가 존재하는지 확인 후 result에 해당 경로를 추가하기
4. 다음 노드는 dx, dy로 이동하면서 백트래킹 이어가기

 

❗코드

import copy
import sys
input = sys.stdin.readline


graph = []
for _ in range(5):
    temp = list(map(int, input().rstrip().split(" ")))
    graph.append(temp)

origin = copy.deepcopy(graph)

r, c = map(int, input().split(" "))


# 좌측 상단 -> 우측 하단
dx = [-1, 0, 0, 1]
dy = [0, 1, -1, 0]


answer = []
result = []

def possible(answer):
    root = []
    for i, j in answer:
        root.append(origin[i][j])

    if answer[0] == [r, c] and len(answer) >= 2 and root.count(1) >= 2:
        return True
    return False



def backtrack(dep, r, c):

    if dep == 4:
        temp = answer[::]
        if possible(temp) and temp not in result:
            result.append(temp)
        return

    if 0<= r and r <5 and 0<=c and c<5 and graph[r][c] != -1:
        temp = origin[r][c]

        graph[r][c] = -1
        answer.append([r, c])

        for i in range(4):
            nx = r + dx[i]
            ny = c + dy[i]
            backtrack(dep+1, nx, ny)

        graph[r][c] = origin[r][c]
        answer.pop()


backtrack(0, r, c)


if result:
    print(1)
else:
    print(0)