백준 20208 진우의 민트초코우유 Python

🐸 문제 정보

20208번: 진우의 민트초코우유

 

🤖 알고리즘

백트래킹

 

⏱️ 풀이 시간

32.00m

 

📝 풀이

처음에 2차원 리스트 보이자마자 BFS로 풀었다가 메모리 터지고... 백트래킹으로 풀어야한다는 것을 알게됐다.

이런 2차원 리스트 주어졌을 때 그냥 생각 안하고 BFS로 푸는 습관좀 고쳐야겠다.

 

백트래킹으로 푸는 경우 풀이는 아래와 같다.

1. 집의 인덱스와, 민트초코 우유가 있는 인덱스 모두를 찾기
2. 집의 인덱스부터 시작해서, 민트초코 우유의 인덱스로 하나씩 이동해보기
3. 이때, 우유 인덱스에 도달했음에도 집으로 돌아갈 체력이 남아있다면, 현재까지 마신 우유 개수 갱신

 

🧑‍💻 나의 답

# pypy3

import sys
input = sys.stdin.readline

n, m, h = list(map(int, input().rstrip().split()))
board = [list(map(int, input().rstrip().split())) for _ in range(n)]
milks = []
hx, hy = 0, 0
res = 0

for i in range(n):
    for j in range(n):
        if board[i][j] == 1:
            hx, hy = i, j
        elif board[i][j] == 2:
            milks.append((i, j))

def bt(px, py, hp, cnt):
    global res
    for nx, ny in milks:
        if board[nx][ny] == 2:
            dist = abs(nx - px) + abs(ny - py)
            if dist <= hp:
                board[nx][ny] = 0
                bt(nx, ny, hp - dist + h, cnt + 1)
                board[nx][ny] = 2
    hdist = abs(hx - px) + abs(hy - py)
    if hdist <= hp:
        res = max(res, cnt)

bt(hx, hy, m, 0)
print(res)