[Silver I] 무한부스터 - 17391
성능 요약
메모리: 34140 KB, 시간: 812 ms
분류
너비 우선 탐색, 다이나믹 프로그래밍, 그래프 이론, 그래프 탐색
문제 설명
카트라이더를 처음 시작하는 카린이 정범이는 어려운 조작법에 실망감이 커져가고 있다. 드리프트, 순간 부스터, 커팅, 톡톡이 등등 어려운 테크닉에 질린 정범이는 그나마 쉬운 ‘숭고한 무한부스터 모드’에 도전해보려고 한다.
‘숭고한 무한부스터 모드’는 크기 N × M 의 직사각형 모양의 맵에서 진행되며, 맵 전체가 단위 격자로 구성되어 있다. 기존의 ‘무한부스터 모드’와는 다르게, 모든 격자 안에는 특정 개수의 부스터 아이템이 위치한다. 이 모드에서 플레이의 방식은 다음과 같다.
처음에 플레이어의 카트바디는 출발지점인 1행 1열에 위치하며, 멈춰 있는 상태이고, 보유하고 있는 부스터 아이템의 개수는 0개이다. 목표는 도착지점인 N행 M열의 격자에 도달하는 것이며, 도달하는 즉시 게임이 종료된다. 카트바디가 격자에 멈추어 있을 때, 격자에 놓여있는 부스터 아이템을 자동으로 전부 습득하게 된다. 이 과정에서 x개를 습득했다면 한 방향을 정해 오른쪽으로 최대 x칸을 가거나, 아래쪽으로 최대 x칸을 이동할 수 있으며, 1칸 단위로 이동하게 된다. 예를 들어 부스터 아이템을 3개 습득했을 때, 오른쪽으로 2칸 이동이나 아래쪽으로 3칸 이동은 가능하지만, 오른쪽으로 1칸 이동 후 아래로 2칸 이동이나 왼쪽으로 1칸 이동이나 아래쪽으로 2.718칸 이동은 불가능하다. 이동 후 멈추면서 보유하고 있던 부스터 아이템은 모두 소진된다.
이동중에 멈추지 않고 지나치는 격자의 부스터 아이템은 습득할 수 없으며, 카트바디는 맵을 벗어나는 방향으로는 움직일 수 없다.
정범이는 ‘숭고한 무한부스터 모드’에서 출발지점부터 도착지점까지 주행하면서 부스터 아이템을 획득하게 되는 격자의 개수를 최소화하고 싶다. 카린이 정범이를 도와주도록 하자.
입력
첫 번째 줄에 맵의 세로 길이와 가로 길이를 나타내는 양의 정수 N과 M이 공백으로 구분되어 주어진다. (1 ≤ N, M ≤ 300)
두 번째 줄부터 N개의 줄에 걸쳐 각 격자에 있는 부스터 아이템 개수인 M개의 양의 정수 aij가 공백으로 구분되어 주어진다. (1 ≤ aij ≤ max(N, M)) aij는 i 행 j 열의 격자에 있는 부스터 아이템 개수이다.
출발지점과 도착지점은 다르다.
출력
첫 번째 줄에 정범이가 맵의 출발지점부터 도착지점까지 이동하면서 부스터 아이템을 획득하게 되는 격자의 최소 개수를 출력한다.
풀이
아이디어
문제가 요구하는 사항만 짧게 정리한다.
- 카트는 (0, 0)에서 시작하며 (N, M)에 도달하면 프로그램을 종료한다.
- 각 격자마다 아이템(부스터)의 개수가 주어지며, 부스터가 있다면 오른쪽 또는 아래쪽으로 최대 부스터 만큼 움직일 수 있다.
- 이때 가장 최소 이동거리를 구해라
문제를 딱 보니 BFS로 풀면 되겠다 라는 생각이 들었고, 우선 그래프 탐색을 구현하는 중에 두번째 조건의 다음 절이 신경이 쓰였다.
최대 부스터만큼 움직일 수 있다.
즉 부스터가 3개가 있다면 1칸부터 3칸까지 자유롭게 움직일 수 있는 경우의 수가 발생한다. 따라서 모든 경우의 수를 커버할 때 메모이제이션을 사용할 필요성을 느꼈다.
메모리를 추가로 사용하는것보다는 visited에 최솟값을 업데이트 하는 방식을 사용해보기로 했다. (변수 visited를 캐시처럼 사용.)
부분문제를 정의해보자.
1. 방문한 위치가 이미 방문한 곳이 아니라면 1부터 까지 모두 방문해본 뒤, 가장 작은 값을 저장한다.
코드
from collections import deque
MAX = 987654321
n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
visited = [[-1] * m for _ in range(n)]
def bfs(x, y, depth):
# print(x, y, depth)
# pprint.pprint(visited)
if x == n and y == m:
# print("ret",depth)
return depth
if x >= n or y >= m:
return MAX
if visited[x][y] != -1:
return visited[x][y]
visited[x][y] = depth
for i in range(graph[x][y], -1, -1):
# print("down,",graph[x][y])
visited[x][y] = min(visited[x][y], bfs(x+i, y, depth+1))
# print("right")
visited[x][y] = min(visited[x][y], bfs(x, y+i, depth + 1))
return visited[x][y]
bfs(0, 0, 0)
print(visited[n-1][m-1] - 1)
from collections import deque
n, m = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
direction = [[0, 1], [1, 0]]
visited = [[0 for _ in range(m)] for _ in range(n)]
visited[0][0] = 0
dq = deque()
dq.append((0, 0))
while dq:
y, x = dq.popleft()
for i in range(2):
nx, ny = x, y
for _ in range(board[y][x]):
nx, ny = nx + direction[i][0], ny + direction[i][1]
if 0 <= nx < n and 0 <= ny < m and visited[nx][ny] == 0:
dq.append((nx, ny))
visited[nx][ny] = visited[x][y] + 1
print(visited[-1][-1])회고
맞왜틀이 많이 나온 문제..
아직 내 첫 코드가 왜 틀린지, 두번째 코드가 왜 맞는 코드랑 다른지 모르겠다.
