[Python] 19238. 스타트 택시

www.acmicpc.net/problem/19238

19238번: 스타트 택시

---

Point

• 처음엔 매 승객마다 최단거리를 구해줬고 시간초과가 났다.
  그럴 필요 없이 현재 택시 위치 기준으로 맵의 최단거리를 구하고 Pop(index) 를 이용해서 연산을 반복한다.

 

메모리 (제한: MB)

124568 KB

시간 (제한: 초)

204 ms

결과

100%

def shortest_path(taxi):
    global n
    dist = [[-1]*n for _ in range(n)]
    queue = [taxi]
    dist[taxi[0]][taxi[1]] = 0
    while queue:
        sy,sx = queue.pop(0)
        for d in ((-1,0),(0,1),(1,0),(0,-1)):
            n_sy = sy + d[0]
            n_sx = sx + d[1]
            if 0<=n_sy<n and 0<=n_sx<n and MAP[n_sy][n_sx] == 0 and dist[n_sy][n_sx] == -1:
                dist[n_sy][n_sx] = dist[sy][sx] + 1
                queue.append((n_sy,n_sx))
    return dist

n,m,feul = map(int, input().split())
MAP = [list(map(int, input().split())) for _ in range(n)]
taxi = list(map(int, input().split()))
passengers = [list(map(int, input().split())) for _ in range(m)]
n_passenger = len(passengers)

while passengers:
    # 최단거리 계산
    p_idx = 0
    min_dist = 10**3
    dist = shortest_path([taxi[0] - 1, taxi[1] - 1])
    for idx in range(len(passengers)):
        _dist = dist[passengers[idx][0] - 1][passengers[idx][1] - 1]
        if _dist == -1:
            continue
        if _dist < min_dist:
            min_dist = _dist
            p_y = passengers[idx][0]
            p_x = passengers[idx][1]
            p_idx = idx
        if _dist == min_dist:
            if passengers[idx][0] < p_y:
                p_y = passengers[idx][0]
                p_x = passengers[idx][1]
                p_idx = idx
            if passengers[idx][0] == p_y:
                if passengers[idx][1] < p_x:
                    p_x = passengers[idx][1]
                    p_idx = idx

    # 벽에 막혀 손님에 갈 수 없음
    if min_dist == 10**3:
        break

    # 선택된 손님 픽업
    y,x,_y,_x = passengers.pop(p_idx)
    taxi = [y,x]
    feul -= min_dist
    if feul <= 0:
        break

    # 이동
    dist = shortest_path([taxi[0] - 1, taxi[1] - 1])
    _dist = dist[_y-1][_x-1]
    if _dist == -1:
        break
    feul -= _dist
    if feul < 0:
        break

    # 도착했을 때
    taxi = [_y,_x]
    n_passenger -= 1
    feul += _dist * 2

if n_passenger > 0:
    print(-1)
else:
    print(feul)

 

문제를 푸는데 도움이 된 테스트 케이스

# Input 5 5 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 3 2 2 4 2 4 2 4 4 4 4 2 4 2 4 2 2 2 5 3 3 # Output 10