[백준_19238]스타트 택시 with Python

백준(BOJ) "삼성 SW 역량 테스트 기출 문제" 문제집: 스타트 택시(골드 4)

문제 출처: www.acmicpc.net/problem/19238

19238번: 스타트 택시

 

1. 알고리즘

• BFS 알고리즘을 사용, 택시와 각 승객들 사이의 거리를 모두 구한다.
  • 이때, 택시가 태울 수 없는 승객이 있다면 중지.
• 조건에 만족하는 승객을 선택, 이동한다. (조건: 최단 거리 > 행 번호 > 열 번호)
  • 연료를 소모한다. 이때 현재 연료로 갈 수 없는 거리라면 중지.
• 승객을 태우고, BFS 알고리즘을 사용하여 출발지에서 도착지까지의 거리를 구한다.
  • 도착지에 도달할 수 없다면 중지.
  • 현재 연료로 갈 수 있다면 연료를 소모, 충전 ▶ 택시 위치 갱신 ▶ 목적지로 이동시킨 승객 제거
  • 현재 연료로 갈 수 없다면 중지.
• M번 반복 후, 남은 승객이 없다면 남은 연료 출력

 

2. 유의 사항

• 경로가 없는 경우 = (동작 중지, -1 출력)
  • 택시가 승객을 태울 수 없는 경우
  • 승객이 도착지까지 갈 수 없는 경우
• 도착지와 출발지
  
  • 승객의 각 출발지는 모두 서로 다르며, 각 손님의 출발지와 목적지는 다르다.
  • 승객 A의 도착지와 승객 B의 출발지는 같을 수 있다. = 승객A를 내려준 후 택시와 승객B의 최단 거리는 0
  • 택시와 승객이 같은 위치에 서 있으면 그 승객까지의 최단 거리는 0

 

3. 어려웠던 점, 해결 방법

• 기준에 따라 승객을 고를 때, sort내장 함수를 쓰는 것이 아닌 if 문으로 승객 데이터를 갱신해주도록 한 코드에 에러가 있었음.
  • 별도의 passengers_distance_temp 리스트에 데이터를 정리, sort로 정렬해주는 것으로 승객 고르는 방법을 바꾸어 해결
• 승객이 목적지에 도달할 수 없는 경우를 고려하지 못했음.
  • type 함수로 반환 데이터 형태를 확인, 목적지에 도착하지 못할 경우를 예외처리해주는 것으로 해결

 

4. 소스 코드

상세 코드 설명은 주석

import sys
from collections import deque
from collections import defaultdict
 
 
#bfs
def calc_distance(start, graph, destination):
    route = deque([start])
    #출발지 0으로 설정
    visited = [[-1]*N for _ in range(N)]
    visited[start[0]][start[1]] = 0
    
    #(택시-승객/출발지-도착지)용도 구별
    if destination:
        destination_flag = True
    else:
        destination_flag = False
    
    while route:
        x, y = route.popleft()
        
        #목적지에 도착했으면 거리 반환
        if destination_flag and (x, y) == destination:
            return visited[x][y]
 
        for idx in range(4):
            nx, ny = x + dx[idx], y + dy[idx]
 
            if 0 <= nx < N and 0 <= ny < N and visited[nx][ny] == -1:
                if graph[nx][ny] == 0:
                    route.append((nx, ny))
                    visited[nx][ny] = visited[x][y] + 1
    
    #택시의 모든 경로에 대한 최단 거리 그래프 반환
    return visited
 
 
if __name__=="__main__":
    N, M, fuel = map(int, sys.stdin.readline().split())
    maps = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
    start_x, start_y = map(int, sys.stdin.readline().split())
    passengers = defaultdict(dict)
    for idx in range(M):
        p_temp = list(map(int, sys.stdin.readline().split()))
        passengers[idx]['start'] = (p_temp[0]-1, p_temp[1]-1)
        passengers[idx]['destination'] = (p_temp[2]-1, p_temp[3]-1)
 
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    start_x, start_y = start_x-1, start_y-1
    for _ in range(M):
        #택시-승객 거리 계산 / 도착지 설정은 None
        passenger_distance = calc_distance((start_x, start_y), maps, None)
        
        #승객을 고르기 위해 (식별 번호, 출발지, 목적지, 택시-출발지 최단 거리) 리스트 생성
        passengers_distance_temp = []
        for p_idx, p in passengers.items():
            p_x, p_y = p['start']
            #택시가 갈 수 없는 위치에 승객이 있으면 바로 중지
            if passenger_distance[p_x][p_y] == -1:
                fuel = -1
                break
            
            passengers_distance_temp.append((p_idx, p['start'], p['destination'],passenger_distance[p_x][p_y]))
        
        #택시가 승객을 태울 수 없는 경우
        if fuel < 0:
            break
        
        #승객 선택 기준에 맞게 정렬, 가장 우선순위가 높은 승객을 min_passenger로 설정
        passengers_distance_temp.sort(key=lambda x: (x[3], x[1][0], x[1][1]))
        min_passenger = passengers_distance_temp[0]
        
        #현재 연료로 승객을 태우러 갈 수 있는지 확인
        if min_passenger[3] <= fuel:
            fuel -= min_passenger[3]
        else:
            break
        
        #승객의 출발지-목적지 거리 계산
        destination_distance = calc_distance(min_passenger[1], maps, min_passenger[2])
        
        #갈 수 있는 경로의 최단 거리 그래프 반환 == 목적지에 도달할 수 없는 경우
        if type(destination_distance) == list:
            break
        #현재 연료로 도착지에 갈 수 있는지 확인
        elif destination_distance <= fuel:
            fuel += destination_distance
            start_x, start_y = min_passenger[2]
            passengers.pop(min_passenger[0])
        else:
            break
    
    #passengers 딕셔너리에 남은 승객이 없다면 남은 연료 출력     
    print(fuel if not passengers else -1)
 

 

 

 

5. 고민

• 승객 데이터 입력을 받을 때 Dictionary로 입력을 받고, 이후 택시 동작 과정에서 따로 리스트를 만들어 동작을 수행한 부분에 대해 구조체 등을 활용했다면 하나의 데이터 구조로 해결할 수 있지 않을까
• (동작 중지, -1 출력)의 경우, fuel을 -1로 값 변경이 꼭 필요했을까. 모든 경우에 대하여 passengers의 데이터가 남아 있기 때문에 fuel을 -1로 처리해주지 않아도 -1 출력이 가능한 것 아닌가. 불필요한 fuel 값 변경 제거

fuel 값 변경 관련 수정 후