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

---

1. 코드

def bfs(start_x, start_y, flag):
    global f
    temp = copy.deepcopy(graph)
    q = deque([(start_x, start_y)])
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n and temp[nx][ny] == 0:
                temp[nx][ny] = temp[x][y] + 1
                q.append((nx, ny))
    temp[start_x][start_y] = 0
    # 택시가 최단거리에 있는 승객을 찾고 태우러 가는 경우
    if not flag:
        min_len = []
        for i in d:
            # 모든 승객의 (거리, 좌표) 값을 저장한다. ex (6, (4, 3))
            min_len.append((temp[i[0]][i[1]], i))
        # sorted() 를 통해 행, 열이 고려된 가장 짧은 거리를 가진 승객을 선택
        # cost = 택시에서 승객까지의 거리
        # passenger_cur_pos = 택시를 기다리고 있는 승객의 좌표
        cost, passenger_cur_pos = sorted(min_len)[0]
        # todo 예외처리: 택시에서 승객까지의 거리가 0인데 출발지와 목적지가 다르다. -> 벽에 막혀서 가지 못한 경우
        if cost == 0:
            if start_x != passenger_cur_pos[0] or start_y != passenger_cur_pos[1]:
                return False
        if f - cost < 0:
            return False
        else:
            f -= cost
            return passenger_cur_pos

    # 택시가 승객의 목적지로 가는 경우
    else:
        # 승객의 목적지 x, y
        passenger_dest_pos_x, passenger_dest_pos_y = d[(start_x, start_y)]
        # 승객의 출발지와 목적지가 같다면 바로 정상적인 종료
        if passenger_dest_pos_x == start_x and y == start_y:
            del d[(start_x, start_y)]
            return [passenger_dest_pos_x, passenger_dest_pos_y]

        cost = temp[passenger_dest_pos_x][passenger_dest_pos_y]
        # todo 예외처리: 출발지와 목적지가 다른데 거리가 0이다. -> 벽에 막혀서 가지 못한 경우
        if f - cost < 0 or cost == 0:
            return False
        else:
            f += cost
            del d[(start_x, start_y)]
            return [passenger_dest_pos_x, passenger_dest_pos_y]


d = defaultdict(int)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
n, m, f = map(int, sys.stdin.readline().rstrip().split())
graph = [list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(n)]
# cur_x, cur_y 는 현재 택시의 좌표
cur_x, cur_y = map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split())
for _ in range(m):
    q, w, e, r = map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split())
    d[(q, w)] = (e, r)  # 승객의 좌표: 승객의 목적지 좌표
while True:
    # d 는 승객의 좌표를 key, 목적지를 value 로 가지고 있는 dict 이다.
    # 승객 한 명을 목적지까지 운행완료하면 del d[key]를 통해 승객을 제거한다. 승객이 모두 제거됐다면 정상적인 운행 종료이다.
    if not d:
        print(f)
        break
    # bfs(...False) = 가장 가까운 승객을 택시에 태우러 운행
    # bfs(...True) = 승객을 목적지까지 운행
    # i = 택시를 기다리는 승객의 현재 좌표
    i = bfs(cur_x, cur_y, False)
    if not i:
        print(-1)
        break
    else:
        p_x, p_y = i
        # j = 승객의 목적지 좌표
        j = bfs(p_x, p_y, True)
        if not j:
            print(-1)
            break
        else:
            cur_x, cur_y = j  # 승객의 목적지가 현재 택시의 좌표로 최신화

---

2. 후기

BFS를 사용한 기초적인 길 찾기 + 구현 문제이다. 고려해야할 예외가 생각보다 많아서 푸는 시간이 오래 걸렸다. 이런 구현 문제들은 많이 풀어보면 확실히 도움이 될 것 같다.

시간복잡도가 널널했기 BFS 한 번 수행할때 마다 모든 그래프를 전부 탐색하고 가장 작은 거리를 가진 승객을 찾는 방법을 사용했다.

86%에서 틀린다면 아래 케이스를 입력 해보자

3 1 100
0 1 0
0 1 0
0 1 0
1 1
1 3 3 3