[ 백준 19238 ] 스타트 택시
🥕 [ 백준 19238 ] 스타트 택시
문제 링크
url : https://www.acmicpc.net/problem/19238
🍒 문제 분석
1. 승객을 태워서 도착지에 가면, 소모한 연료의 두배 충전.
2. 승객을 태우러 갈 때는, 연료 소모만 함.
2. 중간에 연료 바닥 시 영업 종료
3. 우선순위
현재 위치에서 최단 거리 가장 짧은 승객
행 번호가 가장 작은 승객
열 번호가 가장 작은 승객
🍓 내 해결 과정
1. 승객을 태우러 가는 bfs와 승객을 태우고 가는 bfs로 함수를 구분함.
2. 승객을 태우는 우선 순위를 구분하기 위해, 조건에 맞는 승객을 passengers 리스트에 태움
3. 승객의 위치에 해당하는 격자에다가 승객의 회원번호를 저장함 ( 음수 값으로 해서 )
4. 승객의 회원 번호는, 승객의 목적지 조회에 사용됨 (objects 리스트의 인덱스로 사용됨)
5. 승객을 태우기로 확정할 경우, 격자에 승객을 지움
6. 가는 경로 중에 fuel이 음수 값이 되면, 바로 -1을 리턴 함
7. 승객을 태워서 목적지에 가는것은 그냥 최단 경로 알고리즘만 생각하면 돼서 꽤 간단히 구현함.
8. fuel은 visited 격자를 만들어서, 걸리는 시간을 업데이트 하는 동시에 visited를 확인함.
9. visited 격자에 시간 기록은 1부터 시작함에 유의한다. 0에서 시작하면 visited 안한걸로 처리돼서 되돌아간다.
🥑 코드
# https://www.acmicpc.net/problem/19238
import sys
from collections import deque
input = sys.stdin.readline
def isOutside(x, y):
if x < 0 or x >= n or y < 0 or y >= n:
return True
return False
def bfs(s_x, s_y, fuel):
visited = [[0] * n for _ in range(n)]
que = deque()
que.append((s_x, s_y))
visited[s_x][s_y] = 1
# 승객의 우선순위 고려 위해 최단 거리 기록 및 승객 리스트 기록
min_dis = 1e9
passengers = []
while que:
x, y = que.popleft()
# 가는 길에 연료가 바닥난 경로
if fuel - visited[x][y] + 1 < 0:
continue
# 승객인지 확인
if grid[x][y] < 0:
if not passengers or ((visited[x][y] - 1) <= min_dis):
min_dis = visited[x][y] - 1
passengers.append((x, y))
# 해당 경로는 더 이상 탐색 안해도 됨.
continue
for d in direct:
nx, ny = x + d[0], y + d[1]
# border check
if isOutside(nx, ny):
continue
# wall check
if grid[nx][ny] == 1:
continue
# visited check
if visited[nx][ny]:
continue
visited[nx][ny] = visited[x][y] + 1
que.append((nx, ny))
# 중간에 연료가 바닥 났다면
if not passengers:
return -1, -1, -1, -1
passengers.sort()
# 다음에 태울 승객
x, y = passengers[0]
fuel -= visited[x][y] - 1
passenger = -grid[x][y] - 1
grid[x][y] = 0
# 택시 좌표, 남은 연료, 승객 번호
return x, y, fuel, passenger
def go_object(s_x, s_y, o_x, o_y, fuel):
visited = [[0] * n for _ in range(n)]
que = deque()
que.append((s_x, s_y))
visited[s_x][s_y] = 1
while que:
x, y = que.popleft()
# 가는 길에 연료가 바닥난 경로
if fuel - visited[x][y] + 1 < 0:
continue
# 도착지인지 확인
if (o_x, o_y) == (x, y):
fuel += visited[x][y] - 1
return fuel
for d in direct:
nx, ny = x + d[0], y + d[1]
# border check
if isOutside(nx, ny):
continue
# wall check
if grid[nx][ny] == 1:
continue
# visited check
if visited[nx][ny]:
continue
visited[nx][ny] = visited[x][y] + 1
que.append((nx, ny))
# 중간에 연료가 바닥 났다면
return -1
# 행, 승객 수, 초기 연료
n, m, fuel = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(n)]
s_x, s_y = map(int, input().split())
s_x, s_y = s_x - 1, s_y - 1
objects = []
for i in range(1, m + 1):
x, y, o_x, o_y = map(int, input().split())
x, y, o_x, o_y = x - 1, y - 1, o_x - 1, o_y - 1
grid[x][y] = -i
objects.append((o_x, o_y))
direct = [(1, 0), (0, 1), (-1, 0), (0, -1)]
answer = 0
x, y = s_x, s_y
for _ in range(m):
x, y, fuel, passenger = bfs(x, y, fuel)
if fuel < 0:
answer = -1
break
o_x, o_y = objects[passenger]
fuel = go_object(x, y, o_x, o_y, fuel)
x, y = o_x, o_y
if fuel < 0:
answer = -1
break
else:
answer = fuel
print(answer)
"""
1. 도착지 가면, 소모한 연료의 두배 충전
2. 연료 바닥 시 영업 종료
3. 우선순위
현재 위치에서 최단 거리 가장 짧은 승객
행 번호가 가장 작은 승객
열 번호가 가장 작은 승객
"""
🍉 깨달은 점 및 정리
이전에 푼 아기 상어 문제의 확장 판이었다.
바로 풀어서 정답을 냈으면 좋았겠는데 디버그 과정을 거쳤다는 점이 아쉽다.
디버깅 시도
1차 : 문제에서 주어진 좌표가 0부터 시작하는게 아닌걸 발견하고, 해당 부분 수정
2차 : min_dis 를 업데이트 안하고 있는 것을 발견하고 수정
3차 : fuel 계산할 때, visited 에서 1을 빼지 하고, + 1을 한걸 발견하고 수정
4차 : go_object로 승객을 도착지에 태우고 간 이후, 택시 좌표를 목적지 좌표로 업데이트 하지 않을 걸 발견하고 수정
5차 : 스타팅 포인트 좌표를 s_x, s_y로 넣어놔서, 택시 위치가 업데이트 되지 않던걸 보고 수정
정말 많이도 빼먹었다.
구현 문제는 푸는 방법을 알아도 손가락 실수하면 틀려서 정말 풀기 어렵다
많이 풀어서 익숙해지는 수 밖에..