20208번: 진우의 민트초코우유 (acmicpc.net)
20208번: 진우의 민트초코우유
첫번째 줄에 민초마을의 크기인 N과 진우의 초기체력 M, 그리고 민트초코우유를 마실때 마다 증가하는 체력의 양 H가 공백을 두고 주어진다. N, M, H는 모두 10보다 작거나 같은 자연수이다. 두번째
www.acmicpc.net
백트래킹, 브루트포스
주어지는 보드 위에 장애물이 없기 때문에, 우유가 있는 위치까지의 맨하탄 거리를 계산하면 된다.
네 방향으로 탐색하는 알고리즘은 시간초과가 발생하게 된다.
아래와 같은 과정으로 풀이했다.
- 보드 상의 우유 위치를 리스트에 저장한다.
- 우유 리스트를 순회하며 다음 조건을 검사한다.
- 현재까지 마시지 않은 우유인가
- 현재 체력으로 도달할 수 있는 위치인가
- 두 조건을 만족하면 그 우유를 마시고(보드에 0으로 표시), 현재 체력 + 우유 힐 - 이동한 거리 를 계산한다.
- 다음 DFS에 들어간다.
import sys
read = lambda: sys.stdin.readline().strip()
def dfs(jwx, jwy, hp, milk):
global ans
for x, y in milks:
if village[x][y] == 2: # 현재까지 마시지 않은 우유인가
dist = abs(jwx - x) + abs(jwy - y)
if dist <= hp: # 현재 체력으로 도달할 수 있는 위치인가
village[x][y] = 0 # 보드 위에 이번 우유를 마셨다고 표시
dfs(x, y, hp + h - dist, milk + 1)
village[x][y] = 2 # 복구
if abs(jwx - hx) + abs(jwy - hy) <= hp:
ans = max(ans, milk)
n, m, h = map(int, read().split())
village = [list(map(int, read().split())) for _ in range(n)]
milks = [] # 우유의 위치를 저장할 리스트
hx, hy = 0, 0 # 집의 위치
for i in range(n):
for j in range(n):
if village[i][j] == 1:
hx, hy = i, j
if village[i][j] == 2:
milks.append((i, j))
ans = 0
dfs(hx, hy, m, 0)
print(ans)
* pypy3로 제출해야 시간초과가 나지 않는다!