19238: 스타트 택시

풀이 시간

• 1h 54m
• 반례가 안잡혀서 고생하다가 겨우 찾음
  -> "모든 출발지는 서로 다르며, 각 손님의 출발지와 목적지는 다르다"라는 조건에서 간과했던게, 한 승객의 도착지가 다른 승객의 출발지인 경우가 발생 가능하다는 점이다
  -> 처음에는 board에 승객의 출발지는 2로, 승객의 도착지는 3으로 표시한 후에 bfs를 돌렸는데, 이렇게 하면 위의 경우에서 오답을 출력한다

구현 방식

• 한 승객의 도착지가 다른 승객의 출발지인 경우를 처리하기 위해 src, dest, src_dest 변수를 이용했다
  -> src: set 형식으로 승객의 출발지 좌표를 저장
  -> dest: set 형식으로 승객의 도착지 좌표를 저장
  -> src_dest: list 형식으로 승객별 출발지 + 도착지 좌표를 저장

• 전반적인 구현 흐름은 아래와 같다
  while True를 돌면서,
  1) 가까운 승객 찾기 (find_passenger(t_x, t_y))
  2) 승객 데려다주기 (goto_dest(s_x, s_y, d_x, d_y))
  3) 승객의 출발지와 도착지 갱신
  4) 다 데려다 준 경우 (더 이상 승객이 없는 경우) 종료

• 1) find_passenger(t_x, t_y)
  -> 여기서도 예외 사항을 처리해줘야하는데, 현재 택시의 위치가 승객의 출발점인 경우이다. 이 경우를 bfs 탐색 전에 먼저 처리해줘야한다
  -> 그 외의 예외사항
  ---> 벽때문에 승객까지 도달하지 못하는 경우 False 반환
  ---> 연료가 부족하여 승객까지 도달하지 못하는 경우 False 반환

• 2) goto_dest(s_x, s_y, d_x, d_y)
  -> 이 부분은 그냥 nx == d_x and ny == d_y인 경우에 남아있는 연료를 확인하고 도달 가능하다면 현재 연료의 양과 현재 택시의 위치를 갱신하고 True를 반환해주면 된다

• 3) src, dest, src_dest에서 도착한 승객에 대한 정보 지워주기
  -> src, dest, src_dest에서 해당 승객에 대한 좌표를 지워준다

코드

import sys
from collections import deque

dx = (0, 0, -1, 1)
dy = (-1, 1, 0, 0)

def find_passenger(t_x, t_y):
    global energy
    global taxi_x, taxi_y
    
    if (t_x, t_y) in src:
        taxi_x = t_x; taxi_y = t_y
        return True

    queue = deque([]); queue.append((t_x, t_y))
    visit = [[-1] * N for _ in range(N)]
    visit[t_x][t_y] += 1
    passenger = []

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]; ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < N:
                if board[nx][ny] != 1 and visit[nx][ny] == -1:
                    if (nx, ny) in src:
                        visit[nx][ny] = visit[x][y] + 1
                        passenger.append((visit[nx][ny], nx, ny))
                    else:
                        visit[nx][ny] = visit[x][y] + 1
                        queue.append((nx, ny))
    if not passenger:
        return False
    
    passenger.sort()
    passenger = passenger[0]
    if passenger[0] <= energy:
        energy -= passenger[0]
        taxi_x = passenger[1]; taxi_y = passenger[2]
        return True
    else:
        return False

def goto_dest(s_x, s_y, d_x, d_y):
	global energy
    global taxi_x, taxi_y

    queue = deque([]); queue.append((s_x, s_y))
    visit = [[-1] * N for _ in range(N)]
    visit[s_x][s_y] += 1
    distance = 0

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]; ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < N:
                if board[nx][ny] != 1 and visit[nx][ny] == -1:
                    if nx == d_x and ny == d_y:
                        visit[nx][ny] = visit[x][y] + 1
                        distance = visit[nx][ny]
                        if distance <= energy:
                            energy += distance
                            taxi_x = nx; taxi_y = ny
                            return True
                        else:
                            return False
                    else:
                        visit[nx][ny] = visit[x][y] + 1
                        queue.append((nx, ny))
    return False



N, M, energy = map(int, sys.stdin.readline()[:-1].split())
board = []
for n in range(N):
    board.append(list(map(int, sys.stdin.readline()[:-1].split())))

taxi_x, taxi_y = map(int, sys.stdin.readline()[:-1].split())
taxi_x -= 1; taxi_y -= 1
src = set(); dest = set(); src_dest = []
for m in range(M):
    s_x, s_y, d_x, d_y = map(int, sys.stdin.readline()[:-1].split())
    s_x -= 1; s_y -= 1; d_x -= 1; d_y -= 1
    src.add((s_x, s_y)); dest.add((d_x, d_y))
    src_dest.append((s_x, s_y, d_x, d_y)) 

turn = 0
while True:
    ##### 가까운 승객 찾기
    if not find_passenger(taxi_x, taxi_y):
        print(-1)
        exit()
    s_x = taxi_x; s_y = taxi_y
    ##### 승객 데려다주기
    d_x = -1; d_y = -1
    for i in range(len(src_dest)):
        if src_dest[i][0] == s_x and src_dest[i][1] == s_y:
            d_x = src_dest[i][2]; d_y = src_dest[i][3]
    if not goto_dest(s_x, s_y, d_x, d_y):
        print(-1)
        exit()

    ##### 승객의 출발지와 도착지 갱신
    # src, dest, src_dest에서 없애주기
    src.discard((s_x, s_y))
    dest.discard((d_x, d_y))
    src_dest.remove((s_x, s_y, d_x, d_y))

    turn += 1

    ##### 다 데려다 준 경우 (더 이상 승객이 없는 경우) 종료
    if turn == M:
        if len(src_dest) != 0:
            print(-1)
            exit()
        else:
            break

print(energy)

결과

• 반례 찾기가 힘들었다

• 내가 초반에 틀렸던 반례는 아래와 같다 (한 승객의 출발지와 다른 승객의 도착지가 겹쳐지는 경우)

5 5 4
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
3 3
2 2 4 2
4 2 4 4
4 4 2 4
2 4 2 2
2 5 3 3

정답: 10

7 15 9
0 0 0 1 0 0 0
0 0 0 0 1 0 0
0 0 0 0 0 0 0
0 0 1 0 0 0 0
0 1 0 0 1 0 0
0 0 0 1 0 0 0
0 0 0 0 0 0 0
5 6
1 2 2 3
7 3 5 7
3 3 5 6
6 6 3 3
5 6 5 7
4 5 7 3
2 2 3 6
4 4 2 2
7 4 4 7
1 5 6 1
6 2 4 1
1 7 6 1
3 4 5 7
4 2 1 5
4 1 6 3

정답: 57