[백준 19238번] 스타트택시(파이썬)

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

19238번: 스타트 택시

구현할 건

크게 2가지입니다.

 

1. 현재 택시지점 기준

가장 가까운 손님 찾아가기

 

2. 그 손님의 목적지까지 이동하기

 

여기에, 중간에 기름이 떨어지면

바로 영업종료를 해주는 것이 있죠.

 

저는 우직하게

BFS를 사용해서

택시를 기준으로

각각의 손님의 이동거리를 구했습니다.

(중간중간에 벽이 있기 때문에

bfs로 길탐색을 해야합니다.)

그랬더니 예제는 다 맞았으나

시간초과가 발생했습니다.

택시-승객 

이렇게 BFS를 구하다보니

시간이 너무 오래 걸렸습니다.

만약에 승객이 1000명이라면

1000명에 대해서 계속 BFS를 해줘야하는데

그럼 효율이 너무 떨어집니다.

 

시간초과 이슈를 어떻게 해결할까 고민하다가

구글링을 통해 아이디어를 얻었습니다.

먼저, 원래 지도랑 똑같은 크기의 

temp라는 리스트를 만듭니다.

이 리스트의 요소들은

전부 -1로 초기화하고

택시가 있는 지점은 0을 넣습니다.

그 다음, BFS를 시켜주면서

모든 지점을 전부 탐색합니다.

(물론, 이 때 원래 지도에서

벽이 있는 부분은 넘기고요.)

그럼 지도에 택시를 기준으로

얼마나 이동했는지 적혀있습니다.

그 때, 각 사람들마다 좌표를 temp에 입력해서

그 중 최소거리를 구하는 것으로 바뀌었습니다.

이렇게 된다면, 승객이 몇 명이든

BFS를 한 번만 수행하면 됩니다.

-1로 초기화를 해준 이유는

벽으로 가로막혀있어서

이동이 불가능할 때를 나타내기 위해서입니다.

택시가 있는 지점이 0이기 때문에

-1로 초기화를 해주면

탐색이 끝난 뒤에도 -1이라는 의미는

"벽인 지역"이거나

"BFS로 갈 수 없는 지역"입니다.

 

그리고 탑승할 승객을 태운 다음에,

거리가 같은 경우,

열과 행이 가장 작은 승객을 태워야하기 때문에

리스트로 받고 정렬시켰습니다.

굳이 복잡하게

'이 중에서 열이 누가 가장 크고...어...'

하기보다는

간단하게 sort()시키면 됩니다.

 

이후, 도착지까지 가는 것도

이런 방식으로 temp를 만들고

BFS를 시켜준다음

도착지 좌표의 값을 받아

거리를 구했습니다.

한가지 주의할 점은

도착지에 도착하는 순간

연료가 고갈이 되어도 된다는 점

(도착하자마자 다시 충전됨)

 

# 백준 19238번 스타트 택시
from collections import deque

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

graph = [list(map(int, input().split())) for _ in range(N)]

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

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

people = []
for _ in range(M):
    x1, y1, x2, y2 = map(int, input().split())
    x1 -= 1
    y1 -= 1
    x2 -= 1
    y2 -= 1
    # 각 사람의 출발위치, 도착위치를 받음.
    people.append([[x1, y1], [x2, y2]])

time = 0
no = 0

# print(people)

while time < M:
    # 현재 시점을 기준으로 가장 가까운 사람이 누구인지 받기
    # 모든 사람한테 구하면 시간초과가 난다. 가장 가까운 사람만 찾게 길찾기로 BFS구하기
    q = deque()
    q.append([start_x, start_y])
    temp = [[-1] * N for _ in range(N)]
    temp[start_x][start_y] = 0
    min_dis = 1e9
    while q:
        n_x, n_y = q.popleft()
        for d in range(4):
            nx = n_x + dx[d]
            ny = n_y + dy[d]
            if nx < 0 or nx >= N or ny < 0 or ny >= N:
                continue
            if graph[nx][ny] == 1:
                continue
            if temp[nx][ny] >= 0:
                continue
            temp[nx][ny] = temp[n_x][n_y] + 1
            q.append([nx, ny])
    move = []
    # print(temp)
    for i in range(len(people)):
        p_x, p_y = people[i][0]
        now_dis = temp[p_x][p_y]
        if now_dis < 0:
            continue
        if min_dis > now_dis:
            min_dis = now_dis
            move.clear()
            move.append([p_x, p_y, now_dis, i])
        elif min_dis == now_dis:
            move.append([p_x, p_y, now_dis, i])

    move.sort()
    # move가 없는 경우도 실패로 본다
    if len(move) == 0:
        no = 1
        break

    # 가장 가까운 사람한테로 ㄱㄱ+도착지점 받기
    move_x, move_y, use_fuel, pop_people = move.pop(0)
    # print(move_x,move_y)
    # 현자 남은 연료로 이동할 수 있다면
    if fuel - use_fuel > 0:
        fuel -= use_fuel
        start_x = move_x
        start_y = move_y
    # 이동이 불가능하다면 break
    else:
        no = 1
        break
    # print(use_fuel)
    # 이제 도착지점으로 이동한다
    # 승객을 태웠다는 개념으로, 도착받자마자 해당 사람 리스트에서 뺴기
    final_x, final_y = people[pop_people][1]
    people.pop(pop_people)
    # 도착거리까지 최단경로 구하기

    temp = [[-1] * N for _ in range(N)]
    q = deque()
    q.append([start_x, start_y])
    temp[start_x][start_y] = 0
    while q:
        n_x, n_y = q.popleft()
        for d in range(4):
            nx = n_x + dx[d]
            ny = n_y + dy[d]
            if nx < 0 or nx >= N or ny < 0 or ny >= N:
                continue
            if graph[nx][ny] == 1:
                continue
            if temp[nx][ny] > 0:
                continue
            temp[nx][ny] = temp[n_x][n_y] + 1
            q.append([nx, ny])

    now_dis = temp[final_x][final_y]
    # 도착까지 기름이 되는지 판단
    if now_dis < 0:
        no = 1
        break

    if fuel - now_dis >= 0:
        fuel -= now_dis
        start_x = final_x
        start_y = final_y
    else:
        no = 1
        break
    # 도착했다면, 이동하는 동안  소모한 기름 *2를 채워줌
    fuel += now_dis * 2
    time += 1
    if time == M:
        no = 0
        break
    # print(use_fuel)
    # print(now_dis)
    # print(fuel)
if no == 1:
    print(-1)
else:
    print(fuel)

 

https://velog.io/@study-dev347/%EB%B0%B1%EC%A4%80-19238-%EC%8A%A4%ED%83%80%ED%8A%B8-%ED%83%9D%EC%8B%9C

[백준 19238] 스타트 택시(Python)

제가 참고했던 자료입니다.

이 분은 heapq를 쓰셨는데

저는 익숙치가 않아서

그냥 리스트로 받았습니다.

 

BFS를 다룰 때 새로운 시각을 주었던 문제였습니다.