[백준] 19238 스타트 택시, python

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

 

 

 

 

 

bfs를 통해 모든 칸을 탐색하면서 해당위치에 승객이 있다면 (이동해야 하는 거리, 행, 열) 값을 힙에 넣는다.

전부 탐색 후 힙에서 하나를 꺼낸다. 꺼낸 승객은 최소 이동거리를 만족하고, 거리가 같다면 최소행, 최소열인 순으로 힙에서 정렬이 되므로 조건을 만족한다.

만약 승객이 없거나, 연료가 없을 시 종료한다.

 

해당 승객의 위치에서 목적지까지 bfs탐색을 한번 더 한다. 목적지에 도달하기 전에 연료가 0 미만으로 떨어지거나, 목적지로 가는 길이 막힌 경우 종료한다.

여기서 길이 막힌 경우를 빼먹어서 런타임에러가 발생했다. 

 

위 두 과정을 종료되지 않을 때까지 반복해서 구현하였다.

 

 

 

import sys
from collections import deque
import heapq
input = sys.stdin.readline


n, m, fuel = map(int, input().split())
board = [[0]*(n+1)]
for _ in range(n):
    row = [0] + list(map(int, input().split()))
    board.append(row)
startx, starty =   map(int, input().split())
pos = {}
for _ in range(m):
    sx,sy,ex,ey = list(map(int, input().split()))
    pos[(sx,sy)] = (ex,ey)

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


# bfs를 통해 다음 승객을 찾음
def get_next(startx,starty):
    global fuel

    q = deque([[startx,starty]])
    visited = [[0]*(n+1) for _ in range(n+1)]
    visited[startx][starty] = 1
    moves = 0

    heap = []

    while q:
        l = len(q)
        for _ in range(l):
            cx, cy = q.popleft()

            # 연료가 없다면 종료
            if fuel <=0:
                return (-1,-1)

            # 만약 해당 위치에 승객이 있다면 거리, 행, 열 을 힙에 넣음
            if (cx,cy) in pos:
                heapq.heappush(heap,[moves,cx,cy])

            for i in range(4):
                nx,ny = cx+dx[i], cy+dy[i]
                if 1<=nx<=n and 1<=ny<=n:
                    if not visited[nx][ny] and not board[nx][ny]:
                        visited[nx][ny] = 1
                        q.append([nx,ny])
        moves += 1

    # 승객이 없다면 종료
    if not heap:
        return (-1,-1)

    # 힙에서 하나를 꺼냄. 꺼낸 승객은 거리가 최소이고 가장위쪽, 가장 오른쪽에 있음.
    next, nx,ny = heapq.heappop(heap)
    fuel -= next

    return (nx,ny)

# 승객을 목적지 까지 이동
def go_target(startx,starty):
    global fuel

    q = deque([[startx,starty]])
    visited = [[0]*(n+1) for _ in range(n+1)]
    visited[startx][starty] = 1
    moves = 0 

    while q:
        l = len(q)
        for _ in range(l):
            cx, cy = q.popleft()

            # 연료가 없다면 종료
            if fuel < 0:
                return (-1,-1)

            # 도착지점이라면 fuel값을 갱신
            if (cx,cy) == pos[(startx,starty)]:
                del pos[(startx,starty)]
                fuel += moves * 2
                return (cx,cy)

            for i in range(4):
                nx,ny = cx+dx[i], cy+dy[i]
                if 1<=nx<=n and 1<=ny<=n:
                    if not visited[nx][ny] and not board[nx][ny]:
                        visited[nx][ny] = 1
                        q.append([nx,ny])
        moves += 1
        fuel -= 1

    # 도착하는 경로가 없을경우 종료
    return (-1,-1)


# 승객을 선택하고, 목적지로 도달하는 과정을 반복
while True:
    if not pos:
        print(fuel)
        break
    startx,starty = get_next(startx,starty)
    if (startx,starty) == (-1,-1):
        print(-1)
        break
    startx,starty = go_target(startx,starty)
    if (startx,starty) == (-1,-1):
        print(-1)
        break