문제
스타트링크가 "스타트 택시"라는 이름의 택시 사업을 시작했다. 스타트 택시는 특이하게도 손님을 도착지로 데려다줄 때마다 연료가 충전되고, 연료가 바닥나면 그 날의 업무가 끝난다.
택시 기사 최백준은 오늘 M명의 승객을 태우는 것이 목표이다. 백준이 활동할 영역은 N×N 크기의 격자로 나타낼 수 있고, 각 칸은 비어 있거나 벽이 놓여 있다. 택시가 빈칸에 있을 때, 상하좌우로 인접한 빈칸 중 하나로 이동할 수 있다. 알고리즘 경력이 많은 백준은 특정 위치로 이동할 때 항상 최단경로로만 이동한다.
M명의 승객은 빈칸 중 하나에 서 있으며, 다른 빈칸 중 하나로 이동하려고 한다. 여러 승객이 같이 탑승하는 경우는 없다. 따라서 백준은 한 승객을 태워 목적지로 이동시키는 일을 M번 반복해야 한다. 각 승객은 스스로 움직이지 않으며, 출발지에서만 택시에 탈 수 있고, 목적지에서만 택시에서 내릴 수 있다.
백준이 태울 승객을 고를 때는 현재 위치에서 최단거리가 가장 짧은 승객을 고른다. 그런 승객이 여러 명이면 그중 행 번호가 가장 작은 승객을, 그런 승객도 여러 명이면 그중 열 번호가 가장 작은 승객을 고른다. 택시와 승객이 같은 위치에 서 있으면 그 승객까지의 최단거리는 0이다. 연료는 한 칸 이동할 때마다 1만큼 소모된다. 한 승객을 목적지로 성공적으로 이동시키면, 그 승객을 태워 이동하면서 소모한 연료 양의 두 배가 충전된다. 이동하는 도중에 연료가 바닥나면 이동에 실패하고, 그 날의 업무가 끝난다. 승객을 목적지로 이동시킨 동시에 연료가 바닥나는 경우는 실패한 것으로 간주하지 않는다.
모든 승객을 성공적으로 데려다줄 수 있는지 알아내고, 데려다줄 수 있을 경우 최종적으로 남는 연료의 양을 출력하는 프로그램을 작성하시오.
입력
첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다.
다음 줄부터 N개의 줄에 걸쳐 백준이 활동할 영역의 지도가 주어진다. 0은 빈칸, 1은 벽을 나타낸다.
다음 줄에는 백준이 운전을 시작하는 칸의 행 번호와 열 번호가 주어진다. 행과 열 번호는 1 이상 N 이하의 자연수이고, 운전을 시작하는 칸은 빈칸이다.
그다음 줄부터 M개의 줄에 걸쳐 각 승객의 출발지의 행과 열 번호, 그리고 목적지의 행과 열 번호가 주어진다. 모든 출발지와 목적지는 빈칸이고, 모든 출발지는 서로 다르며, 각 손님의 출발지와 목적지는 다르다.
출력
모든 손님을 이동시키고 연료를 충전했을 때 남은 연료의 양을 출력한다. 단, 이동 도중에 연료가 바닥나서 다음 출발지나 목적지로 이동할 수 없으면 -1을 출력한다. 모든 손님을 이동시킬 수 없는 경우에도 -1을 출력한다.
접근
가장 가까운 위치에 있는 승객을 찾고 해당 승객의 목적지까지 이동하는 순서대로 구현하였다.
가까운 위치에 있는 승객을 찾을 때는 거리가 적은 순서대로 찾고 거리가 같을 때는 행 * 100 + 열을 통해 비교한다.
그리고 승객을 찾았다면 해당 승객까지의 거리만큼 연료를 뺀다.
이후 해당 승객에 대한 목적지까지 이동하도록 한다.
이동 후에는 이동거리만큼 더해준다. 목적지까지 도착하면 이동한 거리의 두 배만큼 충전하지만 초기에 이동거리를 빼지않고 이동거리만큼 더하는 것이다.
이때 신경써야할 것은 이동 중에 연료가 0이 되는 것을 확인해야하고, 목적지에 도착하는 동시에 연료가 0이 되더라도 도착하는 것으로 간주해야한다.
구현
- 모두 M번 반복한다.
- M번 동안 승객을 찾고 목적지까지 이동하는 함수를 구현한다.
while M != 0:
taxi_y, taxi_x, target = find_passenger(taxi_y, taxi_x)
if fuel < 0 or taxi_x == -1:
fuel = -1
break
if not move(taxi_y, taxi_x, passengers[target-1][2], passengers[target-1][3]):
fuel = -1
break
M -= 1- 아래는 승객을 찾는 함수이다. 승객의 위치와 승객의 번호를 반환한다.
- board에서 승객을 찾았다면 최소거리인 min_dist를 갱신한다.
- 만약 승객을 찾았을 떄 min_dist와 같을 때는 target으로 비교하여 갱신한다.
def find_passenger(y, x):
global fuel
q = deque()
dist = [[ 0 for _ in range(N)] for _ in range(N)]
target = -1
min_dist = -1
q.append((y, x))
dist[y][x] = 1
while q:
cy, cx = q.popleft()
if min_dist != -1 and min_dist < dist[cy][cx]:
break
if board[cy][cx] > 0:
if min_dist == -1:
target = cy * 100 + cx
min_dist = dist[cy][cx]
elif min_dist != -1 and min_dist == dist[cy][cx]:
if target > cy * 100 + cx:
target = cy * 100 + cx
for d in range(4):
ny = cy + dy[d]
nx = cx + dx[d]
if check_range(ny, nx) and dist[ny][nx] == 0 and board[ny][nx] != 0:
dist[ny][nx] = dist[cy][cx] + 1
q.append((ny, nx))
if target == -1:
return -1, -1, -1
y = target // 100
x = target % 100
passenger = board[y][x]
board[y][x] = -1
fuel -= (min_dist - 1)
return y, x, passenger- 택시의 위치와 목적지를 입력받아 이동한다. 기본적으로 BFS를 통해 탐색한다.
- 이동 중에 연료가 떨어진다면 False를 반환한다.
- 현재 위치가 목적지라면 연료를 이동한 거리만큼 더해주고 택시의 위치를 갱신한 뒤 True를 반환한다.
ef move(sy, sx, ey, ex):
global fuel, taxi_y, taxi_x
q = deque()
dist = [[ 0 for _ in range(N)] for _ in range(N)]
q.append((sy, sx))
dist[sy][sx] = 1
while q:
cy, cx = q.popleft()
if fuel - dist[cy][cx] + 1 < 0:
return False
if cy == ey and cx == ex:
fuel += (dist[cy][cx] - 1)
taxi_y, taxi_x = ey, ex
return True
for d in range(4):
ny = cy + dy[d]
nx = cx + dx[d]
if check_range(ny, nx) and board[ny][nx] != 0 and dist[ny][nx] == 0:
dist[ny][nx] = dist[cy][cx] + 1
q.append((ny, nx))
return False전체 코드
import sys
from _collections import deque
input = sys.stdin.readline
def check_range(y, x):
return (0 <= y < N) and (0 <= x < N)
def find_passenger(y, x):
global fuel
q = deque()
dist = [[ 0 for _ in range(N)] for _ in range(N)]
target = -1
min_dist = -1
q.append((y, x))
dist[y][x] = 1
while q:
cy, cx = q.popleft()
if min_dist != -1 and min_dist < dist[cy][cx]:
break
if board[cy][cx] > 0:
if min_dist == -1:
target = cy * 100 + cx
min_dist = dist[cy][cx]
elif min_dist != -1 and min_dist == dist[cy][cx]:
if target > cy * 100 + cx:
target = cy * 100 + cx
for d in range(4):
ny = cy + dy[d]
nx = cx + dx[d]
if check_range(ny, nx) and dist[ny][nx] == 0 and board[ny][nx] != 0:
dist[ny][nx] = dist[cy][cx] + 1
q.append((ny, nx))
if target == -1:
return -1, -1, -1
y = target // 100
x = target % 100
passenger = board[y][x]
board[y][x] = -1
fuel -= (min_dist - 1)
return y, x, passenger
def move(sy, sx, ey, ex):
global fuel, taxi_y, taxi_x
q = deque()
dist = [[ 0 for _ in range(N)] for _ in range(N)]
q.append((sy, sx))
dist[sy][sx] = 1
while q:
cy, cx = q.popleft()
if fuel - dist[cy][cx] + 1 < 0:
return False
if cy == ey and cx == ex:
fuel += (dist[cy][cx] - 1)
taxi_y, taxi_x = ey, ex
return True
for d in range(4):
ny = cy + dy[d]
nx = cx + dx[d]
if check_range(ny, nx) and board[ny][nx] != 0 and dist[ny][nx] == 0:
dist[ny][nx] = dist[cy][cx] + 1
q.append((ny, nx))
return False
N, M, fuel = map(int, input().split())
board = [ list(map(lambda x: x-1, map(int, input().split()))) for _ in range(N)]
taxi_y, taxi_x = map(lambda x: x-1, map(int, input().split()))
passengers = []
for _ in range(M):
sy, sx, ey, ex = map(lambda x: x-1, map(int, input().split()))
passengers.append((sy, sx, ey, ex))
for key, value in enumerate(passengers):
sy, sx = value[0], value[1]
board[sy][sx] = key + 1
dy = [1, -1, 0, 0]
dx = [0, 0, 1, -1]
while M != 0:
taxi_y, taxi_x, target = find_passenger(taxi_y, taxi_x)
if fuel < 0 or taxi_x == -1:
fuel = -1
break
if not move(taxi_y, taxi_x, passengers[target-1][2], passengers[target-1][3]):
fuel = -1
break
M -= 1
print(fuel)'알고리즘 풀이 > 백준' 카테고리의 다른 글
| [백준 12847] 꿀 아르바이트 (0) | 2021.07.18 |
|---|---|
| [백준 10025] 게으른 백곰 (0) | 2021.07.18 |
| [백준 17140] 이차원 배열과 연산 (0) | 2021.07.17 |
| [백준 14503] 로봇 청소기 (0) | 2021.07.16 |
| [백준 17837] 새로운 게임2 (0) | 2021.07.16 |