[백준 19238번] 스타트 택시 - python

문제 링크

https://www.acmicpc.net/problem/19238

19238번: 스타트 택시

 

풀이 

다익스트라 + 구현 문제 

1. 다익스트라로 현재 위치에 갈 수 있는 최단 거리 구하기 

2. 손님별 현재 위치에서 거리, 행 번호, 열 번호 순으로 정렬 -> 우선순위큐 (heap) 사용 

- 현재 위치에서 도달할 수 있는 승객이 없다면 중단 

3. 갈 승객 위치와 도착위치, 현재위치에서 손님 출발지까지 연료양 저장

4. 승객 제거 

5. 다익스트라로 승객 출발지에서 도착지까지 연료량 구하기 

- 출발지에서 목적지로 갈 수 없다면 중단 

6. 남아있는 연료로 승객을 태우고 목적지까지 갈 수 있는지 확인

- 갈 수 없다면 중담 

7. 연료 두배로 충전하고 현재 위치 갱신 

# https://www.acmicpc.net/problem/19238
import heapq
dx = [-1,1,0,0]
dy = [0,0,1,-1]

def dijkstra(x,y):
    q = []
    heapq.heappush(q, (0,x,y))
    distance = [ [100] * n for _ in range(n)]  
    distance[x][y] = 0 
    
    while q :
        dist, x, y = heapq.heappop(q)
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
        
            if nx < 0 or nx >= n or ny < 0 or ny >= n :
                continue 
            
            if graph[nx][ny] == 1 :
                continue 
        
            if distance[nx][ny] > dist + 1 :
                distance[nx][ny] = dist + 1 
                heapq.heappush(q, (dist+1, nx, ny))
                
    return distance 
    
n, m, fuel = map(int,input().split())

graph = []

for _ in range(n):
    graph.append(list(map(int,input().split())))
    
# 출발지 
x, y = map(int,input().split())

people = []

for _ in range(m):
    people.append(list(map(int,input().split())))


x -= 1 
y -= 1 

while True :
    if len(people) == 0 :
        break
    
    # 현재 위치에서 모든 위치의 최단 거리 구하기 
    start_dist = dijkstra(x,y)
    q = []
    
    # 손님 별 현재 위치에서 갈 수 있는 거리, 행번호, 열번호 순으로 정렬 
    for i in range(len(people)):
        sx, sy, ex, ey = people[i]
        heapq.heappush(q, (start_dist[sx-1][sy-1], sx-1, sy-1, ex-1, ey-1, i))
        
    # 현재 위치에서 가장 가까운 승객 찾기 
    start_fuel, sx, sy, ex, ey, idx = heapq.heappop(q)
    
    # 도달할 수 있는 승객이 없음 
    if start_fuel == 100 :
        fuel = -1
        break     
    
    # 승객 제거 
    people = people[:idx] + people[idx+1:]
    
    # 승객의 출발지에서 승객을 태우고 목적지까지 가는 연료량 구하기 
    end_dist = dijkstra(sx,sy)
    
    end_fuel = end_dist[ex][ey]
    
    # 승객을 태우고 목적지까지 갈 수 없음 
    if end_fuel == 100:
        fuel = -1
        break

    # 연료가 바닥남 
    if start_fuel + end_fuel > fuel :
        fuel = -1
        break

    # 연료 두배 충전하기 
    fuel -= start_fuel
    fuel += end_fuel
    # 현재 택시 위치 갱신 
    x = ex
    y = ey 
    
print(fuel)