[백준 19238] 스타트 택시

문제 바로가기

19238번: 스타트 택시

Logic

Algorithm: 시뮬레이션, BFS

• findDistance(taxi_y, taxi_x, passengerMap): BFS로 현재 택시 위치에서 승객의 위치까지의 그 승객의 index와 최소 거리를 return 하는 함수. 만약 최소 거리가 여러 개라면, 여러 개 모두 return

  • passengerMap: 현재 승객들의 위치의 좌표를 저장하는 이차원 리스트(택시 탑승 완료된 승객은 표시 x)
  • queue: 택시 위치에서 부터 움직일 수 있는 좌표를 저장하는 deque
  • tmpMap: 택시 위치에서 그 좌표까지 가는 데 걸리는 시간을 저장하는 이차원 리스트

• moveTaxi(start_y, start_x, end_y, end_x): BFS로 start지점부터 end지점까지 가는 데 걸리는 시간을 구하여 return

• solution(taxi): passenger 리스트가 빌 때까지 다음을 수행한다.

  1. passenger 리스트를 passengerMap으로 변환(이차원 리스트로, 좌표값을 담고 있음)

  2. findDistance로 최소거리인 승객을 찾음. 최소거리인 승객이 여러 명이라면, 문제에서 주어진 대로 그중 행 번호가 가장 작은 승객을, 그런 승객도 여러 명이면 그중 열 번호가 가장 작은 승객을 고른다.

     newD = sorted(choice, key = lambda x: [x[0], x[1], x[2]])

3. 승객을 골랐다면, 그 승객을 passenger 리스트에서 pop한다.

4. moveTaxi 함수를 호출하여 승객이 내리는 위치까지 가는 데 필요한 연료를 구하고, 최종적으로 남은 연료를 구한다.

Review

처음에 택시에 탈 승객을 구하는 부분에서, 각 승객마다 BFS를 수행하여 시간초과가 났다. BFS 한번만 해서 승객까지의 거리를 다 찾을 수 있는데 .. 왜 그생각을 처음엔 못했을까 ㅜ ㅜ

처음 짠 코드에서 전반적으로 고치느라 시간이 좀 오래 걸렸다.. 아직 부족함을 느끼고 갑니다 ..

Code

from collections import deque

N, M, fuel = map(int, input().split())
Map = [[int(x) for x in input().split()]for y in range(N)]
taxi = [int(x)-1 for x in input().split()]
passenger = [[int(x)-1 for x in input().split()]for y in range(M)]

pos = [[1,0], [-1,0], [0,1], [0,-1]]
Max = 100000000

def isIn(y, x):
    if y >= 0 and y<N and x >=0 and x<N:
        return True
    return False

def findDistance(taxi_y, taxi_x, passengerMap):
    tmpMap = [[0 for x in range(N)]for y in range(N)]
    queue = deque()
    queue.append([taxi_y, taxi_x])
    tmpMap[taxi_y][taxi_x] = 1

    result = []
    while queue:
        curr = queue.popleft()
        if passengerMap[curr[0]][curr[1]] >= 0:
            result.append([passengerMap[curr[0]][curr[1]], tmpMap[curr[0]][curr[1]] - 1])

        for i in range(4):
            ny = curr[0] + pos[i][0]
            nx = curr[1] + pos[i][1]

            if isIn(ny, nx) and Map[ny][nx] == 0 and tmpMap[ny][nx] == 0:
                queue.append([ny, nx])
                tmpMap[ny][nx] = tmpMap[curr[0]][curr[1]] + 1


    if len(result) > 0:
        return result
    return -1

def moveTaxi(start_y, start_x, end_y, end_x):
    tmpMap = [[0 for x in range(N)]for y in range(N)]
    queue = deque()
    queue.append([start_y, start_x])
    tmpMap[start_y][start_x] = 1

    while queue:
        curr = queue.popleft()

        if curr[0] == end_y and curr[1] == end_x:
            return tmpMap[end_y][end_x]-1

        for i in range(4):
            ny = curr[0] + pos[i][0]
            nx = curr[1] + pos[i][1]

            if isIn(ny, nx) and Map[ny][nx] == 0 and tmpMap[ny][nx] == 0:
                queue.append([ny, nx])
                tmpMap[ny][nx] = tmpMap[curr[0]][curr[1]] + 1

    return Max

def solution(taxi):
    global fuel

    while passenger:
        passengerMap = [[-1 for _ in range(N)]for y in range(N)]
        for i in range(len(passenger)):
            passengerMap[passenger[i][0]][passenger[i][1]] = i

        minD = findDistance(taxi[0], taxi[1], passengerMap)
        if minD == -1:
            return -1

        choice = []
        for m in minD:
            choice.append([m[1], passenger[m[0]][0], passenger[m[0]][1], passenger[m[0]][2], passenger[m[0]][3], m[0]])
        newD = sorted(choice, key = lambda x: [x[0], x[1], x[2]])

        select = newD[0]
        passenger.pop(select[5])
        distanceToDest = moveTaxi(select[1], select[2], select[3], select[4])
        waste = fuel - (select[0] + distanceToDest)
        if waste >= 0:
            taxi = [select[3], select[4]]
            fuel = waste + 2*distanceToDest
        else:
            return -1

    return fuel

print(solution(taxi))