[Python] 소가 길을 건나간 이유 7

문제 링크 : https://www.acmicpc.net/problem/14461

14461번: 소가 길을 건너간 이유 7

1. 접근 방법

최단거리 문제인데, 사이클과 방문한 위치를 여러 번 방문할 수 있는 문제여서 다익스트라로 접근했다.

여러 차례 시행착오를 거쳤는데, 완전 탐색이 되지 않도록 하는 것이 이 문제의 핵심인 것 같다.

 

 

2. 풀이 코드

🖥python 코드

import heapq
import sys
input = sys.stdin.readline
MIIS = lambda: map(int, input().split())


n, t = MIIS()
ground = [list(MIIS()) for _ in range(n)]

min_time = 10 ** 10
time_spend = [[min_time for _ in range(n)] for _ in range(n)]

dx, dy = (-1, 0, 1, 0), (0, 1, 0, -1)
# 각 한 칸씩 이동하기 보다, 한번에 3칸씩 이동하는 위치 계산
dx = (-3, -2, -2, -1, -1, -1, 0, 0, 0, 0, 1, 1, 1, 2, 2, 3)
dy = (0, -1, 1, -2, 0, 2, -3, -1, 1, 3, -2, 0, 2, -1, 1, 0)

# 위치, 시간, 3번 이동 표시
heap = [(0, 0, 0)]
while heap:
    time, x, y = heapq.heappop(heap)
    # 도착
    if x == n -1 and y == n - 1:
        if time < min_time:
            min_time = time
        continue
    elif (n - 1 - x) + (n - 1 - y) <= 2:
        if time + (n - 1 - x) + (n - 1 - y) < min_time:
            min_time = time + ((n - 1 - x) + (n - 1 - y)) * t
        continue
    # 최단거리로 이동해도 최소 시간보다 느릴 때
    if time + (n - 1 - x + n - 1 - y) * t >= min_time:
        continue
    # 지금 칸에 최단 시간인지
    if time_spend[x][y] < time:
        continue
    time_spend[x][y] = time
    # 탐색
    for d in range(16):
        nx, ny = x + dx[d], y + dy[d]
        if 0 <= nx < n and 0 <= ny < n:
            if time + t * 3 + ground[nx][ny] < time_spend[nx][ny]:
                heapq.heappush(heap, (time + t * 3 + ground[nx][ny], nx, ny))

print(min_time)

📕코드 설명

각 칸에 이동했을 때, 풀을 먹은 후 몇 번재 칸인지에 따라 문제를 해결할 수도 있다. 그런데 방문 리스트를 잘못 만들었는지 잘 작동하지는 않았다. 그래서 한 번에 3칸씩 이동하는 방법으로 풀었다. 1, 2칸 이동은 걸리는 시간이 중요할 수 있지만, 해당 칸이 어디인지는 중요하지 않다. 3번째 칸의 위치만 탐색하여, 이동에 걸리는 시간 * 3 + 풀의 길이로 해결할 수 있다.

빨간색 위치에 있을 때, 3칸째 이동가능한 범위는 파란색으로 표시되어 있고, 이를 dx, dy 배열로 만들었다.

 

시작 위치에서 3칸째 이동 가능한 위치를 탐색하며 이동 시간 * 3 + 풀의 길이로 각 위치별 최단시간을 업데이트했다.

한 가지 문제는 마지막 도착 칸 기준으로 거리가 2 이하인 경우, 마지막 칸에 도착하고 난 후, 풀을 먹지 않아도 돼서, 이 부분은 따로 처리해주었다.

 

 

3. 생각 정리

단순하게 구현하면 시간초과가 나기 좋다. 사이클과 중복방문이 존재하다 보니, 해당 부분을 잘 처리하지 못해서 시간 초과가 몇 차례 발생했다.

방문 배열을 n*n*3으로 만들어서 하는 방법도 좋은 방법이지만, 이렇게 한번에 몇 칸씩 이동하는 방식으로도 해결 가능해서, 나름 시간 초과가 짜증 나면서도 재미있게 해결했다.