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

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

공부 날짜 : 2022.09.30
정답 참조 여부 : X

택시의 남은 연료로 사람 m명을 태워서 목적지까지 데려다 줄수있는지 판단하고 데려다 줄수 있다면 연료의 남은양을 출력하는 문제이다.

---

bfs로 현 위치에서 최단거리의 손님을 찾고, bfs로 목적지까지 탐색하면서 거리에 따라 연료량을 바꿔주면 되는 문제이다.

주의해야 할점은
1. 손님을 태우러 갈 수 있는가
2. 손님을 태우고 목적지로 갈 수 있는가
3. 택시의 위치에 손님이 있는경우

이 2가지 였다.
연료가 남아있더라도 위 2가지에 해당하여
택시의 위치와 손님의 위치가 벽으로 막히거나 손님과 목적지가 벽으로 막혀있을 경우 불가능으로 출력해야한다.

3번의 경우는 주의해야한다기 보다 쉽게 생각할 수 있는 부분인데 3번을 고려하지 않고 함수를 작성했다가 3번을 적용하기 위해서 함수를 뜯어 고쳐야하기에 그냥 이 부분만 따로 작성해서 기존 함수를 활용하였다.

소스코드

import sys
from copy import deepcopy
input = sys.stdin.readline

###########################################################
#데이터 입력받기
n, m, oil = map(int, input().split())

#도로 상황
graph_data = []
for _ in range(n):
    graph_data.append(list(map(int, input().split())))
    
#연산에 사용할 변수
graph = deepcopy(graph_data)
    
#택시,위치
texi_x, texi_y = map(int, input().split())
texi_postion = [[texi_x - 1, texi_y - 1, 0]]

#손님 위치와 목적지
#1번은 벽이므로 손님번호는 2번부터 체크
guest_goal = [0]*(m+2)
for guest_num in range(2, m+2):
    x, y, goal_x, goal_y = map(int,input().split())
    
    graph[x-1][y-1] = guest_num
    graph_data[x-1][y-1] = guest_num
    guest_goal[guest_num] = [goal_x - 1, goal_y -1]
    
###########################################################
#필요한 기본 정보

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

###########################################################
#택시의 현재위치에서부터 최단거리 손님 찾기
def find_guest(texi_postion):
    #최단 거리의 손님들의 위치가 저장되는 리스트
    guest = []
    
    while texi_postion:
        
        x, y, distance = texi_postion.pop(0)
        
        #손님을 찾았고 현재 탐색하는 위치가 최단거리 손님보다 거리가 멀면 스톱
        if len(guest) != 0 and guest[0][3] <= distance:
            break
        
        distance += 1
        for dir in range(4):
            nx = x + dx[dir]
            ny = y + dy[dir]
            
            #범위 이내이고 벽이 아니며 방문한 칸이 아닐때
            if 0 <= nx < n and 0 <= ny < n and graph[nx][ny] != 1 and graph[nx][ny] != -1:
                #손님이면 손님 리스트에 추가
                if graph[nx][ny] > 1:
                    guest.append([nx, ny, graph[nx][ny], distance])
                #방문 처리후 위치리스트에 추가
                graph[nx][ny] = -1
                texi_postion.append([nx,ny,distance])
    
    #같은 거리의 손님중 행,열번호가 가장작은 손님찾기 위한 정렬
    guest.sort()
    
    #손님을 더 못찾고 돌아가야 할때
    if len(guest) == 0:
        return -1,-1,-1,-1
    
    #손님의 위치, 손님의번호, 거리가 반환됨
    return guest[0]
    
###########################################################
#각 손님의 목적지까지 최단거리   
def go_goal(texi_postion, goal):
    
    while texi_postion:
        x, y, distance = texi_postion.pop(0)
        
        distance += 1
        for dir in range(4):
            nx = x + dx[dir]
            ny = y + dy[dir]
            
            #범위 이내이고 벽이 아닐때
            if 0 <= nx < n and 0 <= ny < n and graph[nx][ny] != 1 and graph[nx][ny] != -1:
                graph[nx][ny] = -1
                texi_postion.append([nx,ny,distance])
                #목표를 찾았으면 위치와 거리를 반환
                if [nx, ny] == goal:
                    return nx, ny, distance
    
    #모든 경로 탐색해도 목적지까지 못갈경우
    return -1, -1, -1
                    
###########################################################
#연산 수행
guest_count = 0

while True:
    #최단거리 손님 탐색후 이동, 연료 소모
    #이미 택시 위치에 손님이 있는지 체크
    if graph[texi_postion[0][0]][texi_postion[0][1]] > 1:
        x, y= texi_postion[0][0], texi_postion[0][1]
        guest_num, distance = graph[x][y], 0
    else:
        graph[texi_postion[0][0]][texi_postion[0][1]] = -1
        x, y, guest_num, distance = find_guest(deepcopy(texi_postion)) 
        
    texi_postion =  [[x,y,0]]
    
    #손님이 남았는데 더 못찾는 경우
    if x == -1:
        print(-1)
        break
        
    
    oil -= distance
    
    #택시경로 초기화
    graph = deepcopy(graph_data)
    #택시의 현위치 저장
    graph[x][y] = -1    
    #현 위치의 손님을 태웠으므로 손님 제거
    graph_data[x][y] = 0
    
    #손님의 목적지의 위치와 필요한 연료탐색
    x, y, need_oil = go_goal(deepcopy(texi_postion), guest_goal[guest_num])
    
    #지금 타신 손님이 목적지에 도착 못할 경우 멈춤
    if x == -1:
        print(-1)
        break
    
    #연료소모
    oil -= need_oil
    
    #연료가 부족할 경우 -1 출력후 반환
    #도착과 동시에 연료가 떨어지는건 괜찮으므로 0보다 작게
    if oil < 0:
        print(-1)
        break
    
    #도착했으면 택시 이동 후 연료 충전
    texi_postion = [[x,y,0]]
    oil += (need_oil * 2)
    
    #택시경로 초기화
    graph = deepcopy(graph_data)
    
    #태워다 드린 손님 카운팅
    guest_count += 1
    
    #손님을 모두 데려다 줬으면 남은 연료량 출력후 멈춤
    if guest_count == m:
        print(oil)
        break