스타트 택시 [삼성 기출]

1. 접근 방법

- 어떤 문제던지 예외 케이스를 고려할 수 있는 역량이 매우 중요하다

-> 예외 케이스를 고려할 수 있는 역량이 곧 실력이다. 

 

- 이 문제에는 두 가지 예외 상황이 있다

(1) 택시가 승객으로 이동할 수 '없는' 경우

-> 칸과 '벽'이 있기 때문에, 택시가 승객으로 이동할 수 '없는' 경우가 발생한다

 

(2) 승객을 태우고 목적지로 이동할 수 '없는'경우

-> 승객을 태우고 목적지로 이동할 때도, 마찬가지로 '벽'으로 인해서 이동할 수 '없는' 경우가 발생한다.

 

- 이러한 예외 케이스들을 잘 고려해줘야 한다

-> 특히, 파이썬에서 TypedError가 나는 상황을 처음 경험했는데, 이는 BFS에서 return이 없어서 발생한 것이었다. 

 

- getTaxiDistance는 승객의 출발지점까지의 각각의 거리와 좌표들을 넣어서 반환한다

-> 이 때, 현재 남아 있는 승객의 수만큼만 구한다

-> 이 때, 벽(1)이 있으므로, distInfo 자체가 존재하지 않을 수 있다.

-> 즉, 승객의 출발지점까지 현재 택시로부터 이동이 불가능할 수 있다.

-> 그러한 경우 while문을 탈출한다 

 

- selectTaxi는 distInfo 기준으로 가장 가까운 승객의 거리를 구한다

-> 만약에 여러 명이라면, row가 가장 작은 것을 구하고, 만약에 row가 같은 것이 여러 명이라면

    col이 가장 작은 것을 구한다

 

- 그 다음 선택된 승객까지의 거리가 현재 gas보다 크다면, 마찬가지로 while문을 탈출한다

-> 그것이 아니라면, gas를 줄이고, 택시를 해당 승객의 출발 지점으로 이동시킨다. 

 

- 그 다음 moveToDestination을 통해서 현재 승객의 출발 지점으로부터 목적지점까지의 거리를 구한다.

-> 이 때, 만약에 벽(1)으로 인해 이동할 수 없는 경우에는 -1을 반환한다. 

 

- 마찬가지로 gas가 이동거리보다 작거나, dist가 -1인 경우에는 while문을 탈출한다

 

- 마지막으로 gas의 양을 줄이고, 택시를 해당 승객의 도착 지점으로 이동시키고, 

  해당 승객이 도착했음을 표시한다.

 

- 이것을 전체 승객이 도착할 때까지 반복해서 적용한다. 

 

 

2. 코드

from collections import deque 

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

board = [] 

for i in range(N):
    row = list(map(int, input().split()))
    board.append(row)
    
    
tx, ty = map(int, input().split())
tx -= 1 
ty -= 1 

taxi = [] 
arrived = [False]*M

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

for i in range(M):
    row = list(map(int, input().split()))
    taxi.append([row[0]-1, row[1]-1, row[2]-1, row[3]-1])
    
    
    
target = len(taxi)

def getTaxiDistance(target): 
    
    visited = [[False]*N for _ in range(N)]
    
    q = deque()
    q.append((tx, ty, 0))
    
    distInfo = [] 
    
    
    while q:
        
        x, y, dist = q.popleft()
        
        for i in range(len(taxi)):
            if arrived[i] == False and x == taxi[i][0] and y == taxi[i][1]:
                distInfo.append([i, x, y, dist])
        
        if len(distInfo) == target:
            break 
                    
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if 0<=nx and nx<N and 0<=ny and ny<N and board[nx][ny] == 0 and visited[nx][ny] == False:
                visited[nx][ny] = True
                q.append((nx, ny, dist+1))
                
    
    return distInfo 



def selectTaxi(distInfo):
    
    
    
    minDist = int(1e9)
    
    for i in range(len(distInfo)):
        if distInfo[i][3] < minDist:
            minDist = distInfo[i][3] 
            
            
    
    minDistTaxis = [] 
    
    for i in range(len(distInfo)):
        if distInfo[i][3] == minDist:
            minDistTaxis.append(distInfo[i])
            
    
    if len(minDistTaxis) == 1:
        return minDistTaxis[0]
        
        
    elif len(minDistTaxis) >= 2:
        minRowTaxis = [] 
        minRow = int(1e9)
        
        for i in range(len(minDistTaxis)):
            if minDistTaxis[i][1] < minRow:
                minRow = minDistTaxis[i][1] 
                
        
        for i in range(len(minDistTaxis)):
            if minRow == minDistTaxis[i][1]:
                minRowTaxis.append(minDistTaxis[i])
                
                
                
        if len(minRowTaxis) == 1:
            return minRowTaxis[0]
            
        
        elif len(minRowTaxis) >= 2:
            minColTaxi = [] 
            minCol = int(1e9)
            
            for i in range(len(minRowTaxis)):
                if minRowTaxis[i][2] < minCol:
                    minCol = minRowTaxis[i][2] 
                    
            
            for i in range(len(minRowTaxis)):
                if minCol == minRowTaxis[i][2]:
                    minColTaxi.append(minRowTaxis[i])
                    
                    
            
            return minColTaxi[0]
                    
            
            
        
    


def moveToDestination(sx, sy, ex, ey):


    visited = [[False]*N for _ in range(N)]
    
    q = deque()
    q.append((sx, sy, 0))
    visited[sx][sy] = True 
    
    
    while q:
        
        x, y, dist = q.popleft() 
        
        if x == ex and y == ey:
            return dist 
        
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if 0<=nx and nx<N and 0<=ny and ny<N and board[nx][ny] == 0 and visited[nx][ny] == False:
                visited[nx][ny] = True
                q.append((nx, ny, dist+1))
    
    
    
    return -1
    






allArrival = True 
cnt = 0 

while True: 
    
    distInfo = getTaxiDistance(target) 
    if len(distInfo) == 0:
        allArrival = False
        break
    
    selectedTaxi = selectTaxi(distInfo)
    
    if gas < selectedTaxi[3]:
        allArrival = False 
        break
    
    gas -= selectedTaxi[3]
    tx = selectedTaxi[1]
    ty = selectedTaxi[2] 
    pos = selectedTaxi[0]
    
    
    dist = moveToDestination(tx, ty, taxi[pos][2], taxi[pos][3])
    
    
    if gas < dist or dist == -1:
        allArrival = False
        break
    
    gas -= dist 
    tx = taxi[pos][2]
    ty = taxi[pos][3] 
    gas += dist*2 
    arrived[pos] = True 
    
    
    cnt += 1 
    target -= 1 
    
    if cnt == len(taxi):
        break 
    
    
    
if allArrival == False:
    print(-1)
else:
    print(gas)