[백준] 20208번(python 파이썬)

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

 

금방 풀릴줄 알았지만 엄청 오래 걸렸다...(항상 이런듯)

 

처음에 집위치에서 상하좌우 모든 곳을 재귀를 돌려서 체력을 계산하면서 민트 초코가 있는곳 까지 가고 집에 도달하면 return 을 하는 식으로 하였지만 시간 초과가 떴다... 생각해보니 모든 경로를 탐색하기 때문에 갔던곳을 또간다. 이 사실을 알지만 처음 푼 방법에서 어떻게 고쳐야 할지 모르겠어서 다 지우고 처음부터 다시 풀기로 하였다.

 

첫풀이

n, hp, hp_puls = map(int, input().split())

graph = [list(map(int, input().split())) for _ in range(n)]
vistied = [[False] * n for _ in range(n)]

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
max_mint = 0
eat_mint = 0
mint_count =0
start_x = -1
start_y = -1

def BackTrack(start_x, start_y, start, depth):
    global hp, eat_mint, max_mint
    if graph[start_x][start_y] == 1 and not start:
        max_mint = max(max_mint, eat_mint)
        if max_mint == mint_count:
            print(max_mint)
            exit(0)
        return
    if hp == 0:
        return
    start = False
    for i in range(4):
        next_x = start_x + dx[i]
        next_y = start_y + dy[i]
        if next_x <= -1 or next_x >= n or next_y <= -1 or next_y >= n:
            continue

        if vistied[next_x][next_y]:
            continue

        if graph[next_x][next_y] == 2:
            hp += hp_puls
            eat_mint += 1

        hp -= 1
        vistied[next_x][next_y] = True
        BackTrack(next_x, next_y, start, depth+1)
        vistied[next_x][next_y] = False

        if graph[next_x][next_y] == 2:
            hp -= hp_puls
            eat_mint -= 1
        hp += 1

    if depth == 0:
        print(max_mint)

for i in range(n):
    for j in range(n):
        if graph[i][j] == 1:
            start_x = i
            start_y = j
        elif graph[i][j] == 2:
            mint_count += 1

BackTrack(start_x, start_y, True, 0)

 

 

두번째로 생각한 방법은 민트초코가 있는곳만 재귀를 돌리느 것이다. 이때 현재 위치에서 현재 체력으로 민트 까지 갈수 있느지를 확인한다. 좌표를 빼고 x y 를 더한후 체력과 비교하면된다. 갈 수 있으면 재귀를 돌린다.

n, hp, hp_puls = map(int, input().split())

graph = [list(map(int, input().split())) for _ in range(n)]

max_mint = 0
eat_mint = 0
start_x = -1
start_y = -1
mint_position = list()

for i in range(n):
    for j in range(n):
        if graph[i][j] == 1:
            start_x = i
            start_y = j
            mint_position.append((i, j))
        elif graph[i][j] == 2:
            mint_position.append((i, j))


def BackTrack(x, y):
    global hp, eat_mint, max_mint

    for i in range(len(mint_position)):
        mint_x, mint_y = mint_position[i]
        if graph[mint_x][mint_y] == 2:
            if hp >= abs(x - mint_x) + abs(y - mint_y):
                graph[mint_x][mint_y] = 0
                hp += hp_puls
                hp -= abs(x - mint_x) + abs(y - mint_y)
                eat_mint += 1
                BackTrack(mint_x, mint_y)
                hp -= hp_puls
                hp += abs(x - mint_x) + abs(y - mint_y)
                eat_mint -= 1
                graph[mint_x][mint_y] = 2
        elif graph[mint_x][mint_y] == 1:
            if hp >= abs(x - mint_x) + abs(y - mint_y):
                max_mint = max(eat_mint, max_mint)

BackTrack(start_x, start_y)
print(max_mint)

 하지만 python3로 실행하면 아직도 시간초과...

pypy3는 잘 나온다.