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

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

19238번: 스타트 택시

최단 거리의 승객을 찾는 bfs1, 승객을 태우고 목적지를 최단 거리로 이동하는 bfs2를 이용하여 탐색한다

중간에 이동할 수 없는 경우가 나오면 -1을 출력하고 종료한다 (bfs는 0을 리턴)

 

bfs1:

- cnt에 이동거리를 저장하면서 현재 이동 거리에서 이동할 수 있는 만큼 이동한다

  fuel이 cnt보다 작으면 0을 리턴한다

  이동한 칸에 승객이 있으면 p에 승객의 좌표를 저장한다

  p에 탑승할 승객의 좌표가 있으면 break 해서 while 문을 빠져나간다

  while문을 나오고 p가 비어있으면 승객한테 이동할 수 없는 경우이므로 0을 리턴한다

 

bfs2:

- 탐색 중간에 fuel이 이동 거리보다 작거나, 목적지로 이동할 수 없으면 0을 리턴한다

  목적지로 이동할 수 있으면 이동거리, 목적지 좌표를 리턴한다

 

1. fuel에는 연료 값을 저장한다. fuel은 이동 거리에 따라서 계속 변한다

2. a에 지도를 저장하고 벽이 있는 칸의 값을 1에서 -1로 바꿔준다

3. 승객이 있는 위치에 번호를 매긴다. 이 번호를 인덱스로 해서 d에 목적지 좌표를 저장한다

   인덱싱을 편하게 하기 위해 앞에서 벽을 -1로 바꿔줬다

4. 승객의 수만큼 반복해서 이동한다.

   만약 현재 택시의 위치에 승객이 있으면 bfs2를 실행해서 목적지로 이동할 수 있는지 탐색한다

5. 이동할 수 있으면 fuel에 이동 거리 length를 더하고 승객이 있는 칸을 0으로 바꿔준다

   택시의 좌표를 목적지로 갱신한 후 continue한다

6. 현재 위치에 승객이 없으면 bfs1을 실행하여 가장 가까운 승객을 찾는다

7. fuel에 이동거리 cnt를 빼주고 p를 정렬한다. 탑승할 승객의 좌표는 p[0] 값이 된다

8. bfs2를 실행해서 fuel에 이동거리 length를 더하고 승객이 있는 칸을 0으로 바꿔준다

   목적지의 좌표를 return하여 택시의 다음 좌표를 갱신한다

9. 모든 탐색을 마치면 fuel을 출력한다

from collections import deque
import sys

input = sys.stdin.readline
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

def bfs1(x, y):
    global fuel
    q1.append([x, y])
    c1[x][y], cnt = 1, 0
    while q1:
        qlen = len(q1)
        p = []
        cnt += 1
        if cnt >= fuel:
            return 0
        for _ in range(qlen):
            x, y = q1.popleft()
            for i in range(4):
                nx, ny = x + dx[i], y + dy[i]
                if 0 <= nx < n and 0 <= ny < n:
                    if a[nx][ny] != -1 and c1[nx][ny] == 0:
                        if a[nx][ny] > 0:
                            p.append([nx, ny])
                        q1.append([nx, ny])
                        c1[nx][ny] = 1
        if p:
            break

    if not p:
        return 0

    fuel -= cnt
    p = sorted(p)
    x, y = p[0]
    res = bfs2(x, y, a[x][y])
    if res == 0:
        return 0
    
    length, nx, ny = res
    fuel += length
    a[x][y] = 0
    return nx, ny


def bfs2(x, y, idx):
    q2.append([x, y])
    c2[x][y] = 0
    while q2:
        x, y = q2.popleft()
        if c2[x][y] >= fuel:
            return 0
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < n:
                if a[nx][ny] != -1 and c2[nx][ny] == -1:
                    q2.append([nx, ny])
                    c2[nx][ny] = c2[x][y] + 1
                    if [nx, ny] == d[idx]:
                        return c2[nx][ny], nx, ny
    return 0


n, m, fuel = map(int, input().split())
a = []
for i in range(n):
    a.append(list(map(int, input().split())))
    for j in range(n):
        if a[i][j] == 1:
            a[i][j] = -1

x, y = map(int, input().split())

d = [[] for _ in range(m+1)]
for i in range(m):
    x1, y1, x2, y2 = map(int, input().split())
    a[x1-1][y1-1] = i+1
    d[i+1] = [x2-1, y2-1]

x -= 1; y -= 1
for _ in range(m):
    q1, c1 = deque(), [[0 for _ in range(n)] for _ in range(n)]
    q2, c2 = deque(), [[-1 for _ in range(n)] for _ in range(n)]

    if a[x][y] > 0:
        res = bfs2(x, y, a[x][y])
        if res == 0:
            print(-1)
            sys.exit()
        length, nx, ny = res
        if length > fuel:
            print(-1)
            sys.exit()
        fuel += length
        a[x][y] = 0
        x, y = nx, ny
        continue

    res = bfs1(x, y)
    if res == 0:
        print(-1)
        sys.exit()
    else:
        x, y = res
print(fuel)