[백준] 19238번 : 스타트 택시

19238번: 스타트 택시

19238번: 스타트 택시

📄 문제개요

택시와 손님이 존재할때, 택시의기름으로 손님을 목적지까지 운송합니다. 운송할때에 기름이 바닥나면 게임이 종료되고, 기름이 바닥나지않고 손님을 목적지까지 운송을 완료하면 택시의 기름은 손님을 운송할때 쓰인 기름 비용의 2배가 됩니다.

모든 손님을 옮긴뒤에, 택시의 기름양을 출력한다. ( 만약, 모든 손님을 이동 할 수 없다면 -1을 출력한다. )

🤔 문제분석

• 손님은 집합자료형 자료구조로 두었고, 손님을 목적지까지 잘 운송 시켜드렸다면 손님을 하나씩 지워나간다.
• 목적진는 딕셔너리 자료구조로 두었고, 손님 식별자인 손님의 시작위치를 key로 그리고 value를 목적지의 위치로 두었다.
• 현재 택시위치에서의 손님까지의 최소 거리를 구해야하는 알고리즘이 필요 하다.
  • BFS를 통하여 손님의 최단 거리를 구한다.
• 손님을 목적지까지 최소거리로 이동시키는 알고리즘이 필요 하다.
  • BFS를 통하여 목적지까지의 최단 거리를 구한다.

📝 의사코드

1. 현재 남아있는 손님이 있는지 확인여부와, 택시의 기름양을 확인한다.
   1. 기름양이 없거나, 손님이 없다면 게임을 종료한다.
2. 현재 택시 위치에서 가장 가까운 손님 후보를 찾는다.
   1. 후보가 없다면 게임을 종료한다.
3. 손님까지 도달한 기름값을 뺀다.
   1. 기름값이 0보다 작거나 같다면 게임을 종료한다.
4. 손님을 목적지까지 운송한다.
5. 손님을 목적지까지 운송한 기름값을 뺀다.
6. 택시의 위치를 갱신한다.
7. 손님을 정상적으로 목적지까지 운송 시켰는지 확인한다.
   1. 정상적으로 운송을 못시켰다면 게임을 종료한다.
8. 목적지까지 도달한 손님을 제거하고, 기름값을 목적지까지 운송한 거리만큼 *2배 늘려준다.
9. 1번으로 반복한다.

💻 코드

from collections import deque
import sys
input = sys.stdin.readline

N, M, T = map(int, input().split())

table = [list(map(int, input().split())) for _ in range(N)]
passenger = set()
destination = {}
    

start_x, start_y = map(int, input().split())

for _ in range(M):
    s_y, s_x, d_y, d_x = map(int, input().split())
    passenger.add((s_y-1, s_x-1))
    destination[(s_y-1, s_x-1)] = (d_y-1, d_x-1)
    
    
# 현재 택시 위치에서, passenger까지의 최단경로를 구한다.
def min_distacne(s_y, s_x, passenger):
    queue = deque()
    visited = [[False for _ in range(N)] for _ in range(N)]
    visited[s_y][s_x] = True
    queue.append((s_y, s_x, 0))
    dest = []
    while queue:
        y, x , cost = queue.popleft()
        if (y, x) in passenger:
            dest.append((y, x, cost))
        
        for dy, dx in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            ny, nx = dy + y, dx + x
            if N > ny >=0 and N > nx >=0 and table[ny][nx] == 0 and not visited[ny][nx]:
                visited[ny][nx] = True
                queue.append((ny, nx, cost + 1))
        
    if not dest:
        return None
    else:
        dest.sort(key=lambda x:(x[2], x[0], x[1]))
        return dest[0]

def move_passenger(s_y, s_x, t_y, t_x):
    queue = deque()
    visited = [[False for _ in range(N)] for _ in range(N)]
    visited[s_y][s_x] = True
    queue.append((s_y, s_x, 0))
    while queue:
        y, x , cost = queue.popleft()
        if y == t_y and x == t_x:
            return (y, x, cost)
        
        for dy, dx in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            ny, nx = dy + y, dx + x
            if N > ny >=0 and N > nx >=0 and table[ny][nx] == 0 and not visited[ny][nx]:
                visited[ny][nx] = True
                queue.append((ny, nx, cost + 1))
                
    return None

start_x -= 1
start_y -= 1

while passenger and T:
    t_passenger = min_distacne(start_x, start_y, passenger)
    if t_passenger is None:
        #print("손님없음")
        break
    
    T -= t_passenger[2]
    
    if T <= 0:
        #print("기름없음")
        break
    
    #print("이동후 기름", T)
    
    dest_y, dest_x = destination[(t_passenger[0], t_passenger[1])]
    
    moved = move_passenger(t_passenger[0], t_passenger[1], dest_y, dest_x)
    
    if moved is None:
        #print("손님을 옮길 수 없음.")
        break
    
    start_x, start_y = moved[:2]
    T -= moved[2]
    
    # 기름이 0이상일경우는 승객을 옮겼음.
    if T >= 0:
        passenger.remove((t_passenger[0], t_passenger[1]))
        T += (moved[2]) * 2
    
    #print("승객후 기름", T)

if passenger:
    print(-1)
else:
    print(T)

🎯 피드백 및 개선사항

조건을 정확하게 기록하지 않아서 문제를 중간에 풀때에 헛갈리는 경우가 있어서 문제의 주어진 조건을 다른곳에 잘 기록해두어 빼먹지 않아야겠다.

❓다른사람은 어떻게 풀었을까?

구현문제로 모든 사람들이 비슷하게 풀었다.