137. [삼성기출33]Python 백준 19238 번 스타트 택시 자세한 설명 및 반례
안녕하세요 코딩하는 덕구입니다.
파이썬 백준 19238 스타트 택시입니다.
https://www.acmicpc.net/problem/19238
19238번: 스타트 택시
첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다
www.acmicpc.net
백준 19238 스타트 택시 파이썬 코드입니다. 설명은 아래에 있습니다.
from collections import deque
N, M, fuel = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
x, y = map(int, input().split())
x, y = x-1, y-1
info = [list(map(int, input().split())) for _ in range(M)]
#승객 2 도착 3
index_p = {}
cord_d = {}
for num, i in enumerate(info):
x1, y1, x2, y2 = i
board[x1 - 1][y1 - 1] = 2
index_p[(x1 - 1, y1 - 1)] = num
cord_d[num] = [x2 - 1, y2 - 1]
dx = [-1, 0, 0, 1]
dy = [0, -1, 1, 0]
def solve():
global x, y, fuel
while M > 0:
x, y, fuel, destx, desty = find_passenger(x, y, fuel)
if fuel < 0:
return -1
fuel = go_destination(x, y, fuel, destx, desty)
x, y = destx, desty
if fuel < 0:
return -1
return fuel
def find_passenger(x, y, fuel):
global M
distance = 1e9
candidate = [] #승객 후보
queue = deque()
queue.append([x, y, fuel])
visited = [[False for _ in range(N)] for _ in range(N)]
visited[x][y] = True
while queue:
x, y, fuel = queue.popleft()
start = fuel
if board[x][y] == 2: #도착한 경우
if fuel >= 0:
if start - fuel <= distance:
candidate.append([x, y, fuel])
distance = start - fuel
for i in range(4):
nx, ny = dx[i] + x, dy[i] + y
if 0 <= nx < N and 0 <= ny < N:
if not visited[nx][ny] and board[nx][ny] != 1 and 0 < fuel:
visited[nx][ny] = True
queue.append([nx, ny, fuel - 1])
if candidate:
candidate.sort(key=lambda x : (-x[2], x[0], x[1]))
x, y, fuel= candidate[0]
board[x][y] = 0
M -= 1
num = index_p[(x, y)]
destx, desty = cord_d[num]
return [x, y, fuel, destx, desty]
return [-1, -1, -1, -1, -1] #갈 곳이 없는 경우
def go_destination(x, y, fuel, destx, desty):
queue = deque()
origin = fuel
queue.append([x, y, fuel])
visited = [[False for _ in range(N)] for _ in range(N)]
visited[x][y] = True
while queue:
x, y, fuel = queue.popleft()
if [x, y] == [destx, desty]:
if fuel < 0:
return -1
return fuel + (origin - fuel) * 2
for i in range(4):
nx, ny = dx[i] + x, dy[i] + y
if 0 <= nx < N and 0 <= ny < N:
if not visited[nx][ny] and board[nx][ny] != 1 and fuel > 0:
visited[nx][ny] = True
queue.append([nx, ny, fuel - 1])
return -1
print(solve())
문제 접근
1. 가장 가까운 승객을 찾기위한 BFS 1번
2. 최단 거리로 도착에 가기위한 BFS 1번
3. 위의 BFS들을 연료가 떨어지거나 모든 승객을 태울 때 까지 반복합니다.
4. 최단거리의 승객이 여러명인 경우 열과 행이 가장 작은 숫자인 승객을 태웁니다.
이때 BFS탐색을 [상, 좌, 우, 하]순으로 시도하고, 가장 먼저 만난 승객을 태우게 되면
4번의 조건을 통과하지 못합니다.
[좌, 좌, 좌], [우, 우, 상] 의 경우 1 번째 경우가 먼저 탐색이 되지만
우선순위에서 2 번째 경우가 앞서는 반례가 있습니다.
Python 코드 구현
그래프의 상태, 승객과, 도착지, 방향을 구현하기 위한 코드들을 작성합니다.
index_p의 경우 좌표를 넣으면 몇번 승객인지 알려주는 dictionary 입니다.
cord_d는 번호를 넣으면 도착 좌표를 알려줍니다.
from collections import deque
N, M, fuel = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
x, y = map(int, input().split())
x, y = x-1, y-1
info = [list(map(int, input().split())) for _ in range(M)]
#승객 2 도착 3
index_p = {}
cord_d = {}
for num, i in enumerate(info):
x1, y1, x2, y2 = i
board[x1 - 1][y1 - 1] = 2
index_p[(x1 - 1, y1 - 1)] = num
cord_d[num] = [x2 - 1, y2 - 1]
dx = [-1, 0, 0, 1]
dy = [0, -1, 1, 0]
1. find_passenger 를 통해 조건에 맞는 최단거리 승객을 찾습니다.
2. go_destination을 통해 최단거리로 도착지로 이동한 후 연료를 채웁니다.
3. 모든 승객을 다 태울때 까지 반복합니다.
4. 이때 연료가 다 떨어지거나 승객 혹은 도착지를 찾을 수 없으면 -1 을 return 합니다.
def solve():
global x, y, fuel
while M > 0:
x, y, fuel, destx, desty = find_passenger(x, y, fuel)
if fuel < 0:
return -1
fuel = go_destination(x, y, fuel, destx, desty)
x, y = destx, desty
if fuel < 0:
return -1
return fuelprint(solve())
조건에 맞는 최단거리의 승객을 찾는 함수 find_passenger입니다.
candidate는 승객 후보를 담는 list입니다.
승객을 찾게되면 기존보다 distance가 크지 않은지 확인 한 후, distance를 업데이트 합니다.
조건에 맞다면 cansdidate에 추가합니다.
def find_passenger(x, y, fuel):
global M
distance = 1e9
candidate = [] #승객 후보
queue = deque()
queue.append([x, y, fuel])
visited = [[False for _ in range(N)] for _ in range(N)]
visited[x][y] = True
while queue:
x, y, fuel = queue.popleft()
start = fuel
if board[x][y] == 2: #도착한 경우
if fuel >= 0:
if start - fuel <= distance:
candidate.append([x, y, fuel])
distance = start - fuel
BFS 탐색은 이렇게 진행해주시고
for i in range(4):
nx, ny = dx[i] + x, dy[i] + y
if 0 <= nx < N and 0 <= ny < N:
if not visited[nx][ny] and board[nx][ny] != 1 and 0 < fuel:
visited[nx][ny] = True
queue.append([nx, ny, fuel - 1])
탐색이 끝나면 후보가 있는지 확인 한 후
연료가 가장 많이 남고, 좌표가 작은 순으로 후보를 정렬 합니다.
이후 택시 좌표, 남은 연료, 도착 좌표를 return 합니다.
if candidate:
candidate.sort(key=lambda x : (-x[2], x[0], x[1]))
x, y, fuel= candidate[0]
board[x][y] = 0
M -= 1
num = index_p[(x, y)]
destx, desty = cord_d[num]
return [x, y, fuel, destx, desty]
return [-1, -1, -1, -1, -1] #갈 곳이 없는 경우
다음은 도착지점으로 가는 함수 go_destination입니다.
사용한 연료를 * 2를 해주어 남은 연료와 더해 연료를 업데이트 합니다.
def go_destination(x, y, fuel, destx, desty):
queue = deque()
origin = fuel
queue.append([x, y, fuel])
visited = [[False for _ in range(N)] for _ in range(N)]
visited[x][y] = True
while queue:
x, y, fuel = queue.popleft()
if [x, y] == [destx, desty]:
if fuel < 0:
return -1
return fuel + (origin - fuel) * 2
for i in range(4):
nx, ny = dx[i] + x, dy[i] + y
if 0 <= nx < N and 0 <= ny < N:
if not visited[nx][ny] and board[nx][ny] != 1 and fuel > 0:
visited[nx][ny] = True
queue.append([nx, ny, fuel - 1])
return -1
백준 19238 스타트 택시 Python 코드였습니다.
감사합니다.