백준_20208_진우의 민트초코우유(python)

★ 접근

문제를 보면 4방향으로 이동하면서 탐색하는 백트래킹을 떠올리기 쉽다. 하지만 n의 최대 크기가 10이고 방문했던 곳을 무한히 방문할 수 있기 때문에 백트래킹을 한다면 시간초과가 난다. 그렇다면 어떻게 해야할까? 우유가 있는 좌표를 따로 담아 놓는 백트래킹을 해야한다.

 

★ 풀이

1. 진우의 초기 좌표와 우유들이 있는 좌표를 구한다.

2. 

for i in range(len(mint)):

우유들을 처음부터 하나씩 꺼내보면서

if not visited[i]:

방문하지 않았으면서 현재 체력으로 꺼낸 우유 좌표까지 도달할 수 있다면 그 지역까지 가면서 dfs를 해주면 된다.

 

 

★ 코드

import sys
input = sys.stdin.readline
n,m,h = map(int,input().split())
data = []
mint = []
sr,sc = 0,0
for i in range(n):
    temp = list(map(int,input().split()))
    for j in range(n):
        if temp[j] == 1:
            sr,sc = i,j
        elif temp[j] == 2:
            mint.append((i,j))
    data.append(temp)
dx = [-1,1,0,0]
dy = [0,0,-1,1]
visited = [0] * len(mint)
ans = 0
def solve(x,y,hp,count):
    global ans 
    for i in range(len(mint)):
        if not visited[i]:
            temp = abs(mint[i][0] - x) + abs(mint[i][1] - y)
            if hp >= temp: 
                visited[i] = 1
                solve(mint[i][0],mint[i][1],hp-temp+h,count+1)
                visited[i] = 0
    if hp >= abs(sr-x) + abs(sc-y):
        ans = max(ans,count)

solve(sr,sc,m,0)
print(ans)

★ 회고

흠.... 처음에는 무조건 집으로 돌아야하니 현재 체력 + 회복되는 체력 >= abs(현재 좌표 - 우유) + abs(우유 - 집) 했었다. 당연히 틀렸다. 현재 내가 가고자 하는 우유가 비록 먹고나서 집으로는 못 돌아와도 다음 우유가 있는 지역들을 돌아다니다 보면 집으로 돌아올 수도 있기 때문이다. 당연한건데 흠... 아쉽다