19238번 - 스타트 택시

문제

 

19238번: 스타트 택시 (acmicpc.net)

19238번: 스타트 택시

풀이 1

문제에는 명시되어 있지 않지만, 각 손님의 출발지점은 다르지만 도착지점은 같을 수 있다.

 

처음에는 각 손님에 대해서 거리를 구해  heapq에 넣었지만, 시간초과가 발생한다.

택시의 위치부터 보드 전체를 탐색하며 남아있는 손님을 탐색하면 시간초과가 발생하지 않는다.

여러 제한 조건들을 유의해서 풀이해야하는 문제이다.

from collections import deque
import heapq

# 북,동,남,서
dRow = [-1,0,1,0]
dCol = [0,-1,0,1]

n,m,fuel = map(int,input().split())
board = [[1]*(n+2)]
completed = [[False]*(n + 2) for _ in range(n + 2)]
for _ in range(n):
    board.append([1]+list(map(int, input().split()))+[1])
board.append([1]*(n+2))
taxi = list(map(int, input().split()))
psg = [[-1] * (n + 2) for _ in range(n + 2)]
dest = {}
for i in range(m):
    x,y,r,c = map(int, input().split())
    psg[x][y] = i
    dest[(x,y)] = (r,c)
# 목표 승객 수
obj = m

INF = int(1e9)

def get_distance(now,target):
    visited = [[0]*(n+2) for _ in range(n+2)]
    q = deque()
    q.append(now)
    visited[now[0]][now[1]] = 1
    while q:
        row,col = q.popleft()
        for i in range(4):
            nRow, nCol = row + dRow[i], col + dCol[i]
            if board[nRow][nCol] == 0 and visited[nRow][nCol] == 0:
                visited[nRow][nCol] = visited[row][col] + 1
                if not (row,col) == target:
                    q.append((nRow,nCol))
    return visited[target[0]][target[1]] - 1


def get_heap(x,y):
    heap = []
    visited = [[0] * (n + 2) for _ in range(n + 2)]
    visited[x][y] = 1
    q = deque()
    q.append((x,y))
    if psg[x][y] > -1:
        heapq.heappush(heap,((0,x,y)))
        return heap
    while q:
        row,col = q.popleft()
        for i in range(4):
            nRow, nCol = row + dRow[i], col + dCol[i]
            if board[nRow][nCol] == 0 and visited[nRow][nCol] == 0:
                visited[nRow][nCol] = visited[row][col] + 1
                if psg[nRow][nCol] > -1:
                    distance = visited[nRow][nCol] - 1
                    heapq.heappush(heap,((distance,nRow,nCol)))
                q.append((nRow,nCol))
    return heap


for _ in range(m):
    # 손님과 거리 탐색
    tr,tc = taxi
    heap = get_heap(tr,tc)
    if not heap:
        break
    # 손님한테 이동
    distance,x,y = heap[0]
    taxi[0], taxi[1] = x, y
    # 연료 소모
    fuel -= distance
    if fuel <= 0:
        break
    # 목적지까지 이동
    r,c = dest[(x,y)]
    taxi[0], taxi[1] = r, c
    distance = get_distance((x,y),(r,c))
    if distance == -1:
        break
    # 연료 소모
    fuel -= distance
    if fuel < 0:
        break
    else:
        psg[x][y] = -1
        obj -= 1
        fuel += 2*distance

if obj == 0:
    print(fuel)
else:
    print(-1)

풀이 2

손님이 도달할 수 없는 곳에 있는 경우, 도착지가 도달할 수 없는 곳에 있는 경우, 출발지와 목적지가 같은 경우, 택시와 손님이 같은 위치에 있는 경우 등을 고려해서 코드를 짜야한다. BFS로 탐색할 때 가지치기를 적절히 하면 제한조건들을 만족시키며 구현할 수 있다.

import heapq
from collections import deque

#  동 남 서 북
dRow = [0,1,0,-1]
dCol = [1,0,-1,0]

N,M,fuel = map(int,input().split())
map_board = [[0]*(N+1)]
for _ in range(N):
    map_board.append([0] + list(map(int, input().split())))
sr,sc = map(int,input().split())
arv_board = [[[] for col in range(N+1)] for row in range(N+1)]
for _ in range(M):
    r,c,x,y = map(int,input().split())
    arv_board[r][c] = [x,y]


for _ in range(M):
    # 손님 탐색 후 이동
    # 손님이 택시랑 같은 칸에 있으면 탐색할 필요 없음
    if not arv_board[sr][sc]:
        heap =  []
        visited = [[0] * (N+1) for __ in range(N+1)]
        visited[sr][sc] = 1
        q = deque()
        q.append((sr, sc, 0))
        while q:
            row, col, cnt = q.popleft()
            if arv_board[row][col]:
                heapq.heappush(heap, (cnt, row, col))
            for dir in range(4):
                nRow, nCol = row + dRow[dir], col + dCol[dir]
                if 1 <= nRow <= N and 1 <= nCol <= N and visited[nRow][nCol] == 0 and map_board[nRow][nCol] == 0:
                    if cnt + 1 > fuel or (heap and cnt + 1 > heap[0][0]):  # 가지치기
                        continue
                    visited[nRow][nCol] = 1
                    q.append((nRow, nCol, cnt + 1))
        if not heap: # 손님이 도달할 수 없는 곳에 있음
            print(-1)
            break
        dist,sr,sc = heap[0]
        fuel -= dist
    # 손님 태우고 목적지 까지의 탐색 및 이동
    tr,tc = arv_board[sr][sc]
    arv_board[sr][sc].clear()
    visited = [[0] * (N+1) for __ in range(N+1)]
    visited[sr][sc] = 1
    dist = -1
    q = deque()
    q.append((sr,sc,0))
    while q:
        row,col,cnt = q.popleft()
        if [row,col] == [tr,tc]: # 탐색에 영향 없어서 이렇게 해도 괜찮음
            dist,sr,sc = cnt,row,col
            break
        for dir in range(4):
            nRow,nCol = row+dRow[dir],col+dCol[dir]
            if 1 <= nRow <= N and 1 <= nCol <= N and visited[nRow][nCol] == 0 and map_board[nRow][nCol] == 0:
                if cnt + 1 <= fuel: # 도달 가능한 곳만 탐색
                    visited[nRow][nCol] = 1
                    q.append((nRow,nCol,cnt+1))
    if dist == -1: # 도착시점에 연료가 0이 되는건 괜찮다.
        print(-1)
        break
    fuel -= dist
    fuel += 2*dist
else:
    print(fuel)