문제 링크

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

문제 설명

• 택시 승객 태우고 데려다 주고 반복
• 한 칸에 1씩 연료 소모
• 데려다 주면 소모한 연료 * 2 충전
• 모두 데려다 줄 수 있으면 남은 연료 출력
• 아니면 -1 출력

풀이

• BFS로 가장 가까운 승객 찾기, 데려다 주기 반복

후기

• 지난번에도 같은 실수를 했던 것 같은데
• 상, 좌, 우, 하 순으로 BFS 돌면서 제일 처음 만나는 위치를 리턴했다.
• 이러면 반례가 발생한다ㅜ

코드

import sys
from collections import deque

def solution():
    read = sys.stdin.readline
    n, m, fuel = map(int, read().split())
    board = [0]+[[0]+list(map(int, read().split())) for _ in range(n)]
    ty, tx = map(int, read().split())
    guests = dict()
    for _ in range(m):
        sy, sx, ey, ex = map(int, read().split())
        guests[(sy, sx)] = {(ey, ex)}

    possible = True
    while guests:
        # 최단 거리 승객 위치 찾기
        dist, sy, sx = bfs(ty, tx, n, board, guests)
        if dist > fuel:
            possible = False
            break
        fuel -= dist

        # 도착지 가기
        dist, ey, ex = bfs(sy, sx, n, board, guests[(sy, sx)])
        if dist > fuel:
            possible = False
            break
        fuel -= dist

        fuel += dist * 2
        del guests[(sy, sx)]
        ty, tx = ey, ex

    if possible:
        print(fuel)
    else:
        print(-1)

def bfs(sy, sx, n, board, dest):
    guests = []
    dy, dx = [-1,0,0,1], [0, -1, 1, 0]
    visited = [[0]*(n+1) for _ in range(n+1)]
    visited[sy][sx] = 1
    q = deque([[sy, sx, 0]])
    while q:
        cy, cx, cd = q.popleft()
        if (cy, cx) in dest:
            guests.append([cd,cy,cx])
        for d in range(4):
            ny, nx = cy+dy[d], cx+dx[d]
            if 1 <= ny <= n and 1 <= nx <= n:
                if board[ny][nx] == 0 and not visited[ny][nx]:
                    visited[ny][nx] = 1
                    q.append([ny,nx,cd+1])
    if guests:
        guests.sort()
        return guests[0]
    return float('inf'), -1, -1

solution()