Baekjoon 19238 - 스타트 택시 (클릭 시 이동)
문제
스타트링크가 "스타트 택시"라는 이름의 택시 사업을 시작했다. 스타트 택시는 특이하게도 손님을 도착지로 데려다줄 때마다 연료가 충전되고, 연료가 바닥나면 그 날의 업무가 끝난다.
택시 기사 최백준은 오늘 M명의 승객을 태우는 것이 목표이다. 백준이 활동할 영역은 N×N 크기의 격자로 나타낼 수 있고, 각 칸은 비어 있거나 벽이 놓여 있다. 택시가 빈칸에 있을 때, 상하좌우로 인접한 빈칸 중 하나로 이동할 수 있다. 알고리즘 경력이 많은 백준은 특정 위치로 이동할 때 항상 최단경로로만 이동한다.
M명의 승객은 빈칸 중 하나에 서 있으며, 다른 빈칸 중 하나로 이동하려고 한다. 여러 승객이 같이 탑승하는 경우는 없다. 따라서 백준은 한 승객을 태워 목적지로 이동시키는 일을 M번 반복해야 한다. 각 승객은 스스로 움직이지 않으며, 출발지에서만 택시에 탈 수 있고, 목적지에서만 택시에서 내릴 수 있다.
백준이 태울 승객을 고를 때는 현재 위치에서 최단거리가 가장 짧은 승객을 고른다. 그런 승객이 여러 명이면 그중 행 번호가 가장 작은 승객을, 그런 승객도 여러 명이면 그중 열 번호가 가장 작은 승객을 고른다. 택시와 승객이 같은 위치에 서 있으면 그 승객까지의 최단거리는 0이다. 연료는 한 칸 이동할 때마다 1만큼 소모된다. 한 승객을 목적지로 성공적으로 이동시키면, 그 승객을 태워 이동하면서 소모한 연료 양의 두 배가 충전된다. 이동하는 도중에 연료가 바닥나면 이동에 실패하고, 그 날의 업무가 끝난다. 승객을 목적지로 이동시킨 동시에 연료가 바닥나는 경우는 실패한 것으로 간주하지 않는다.
<그림 1>
<그림 1>은 택시가 활동할 영역의 지도를 나타내며, 택시와 세 명의 승객의 출발지와 목적지가 표시되어 있다. 택시의 현재 연료 양은 15이다. 현재 택시에서 각 손님까지의 최단거리는 각각 9, 6, 7이므로, 택시는 2번 승객의 출발지로 이동한다.
<그림 2> <그림 3> <그림 2>는 택시가 2번 승객의 출발지로 가는 경로를, <그림 3>은 2번 승객의 출발지에서 목적지로 가는 경로를 나타낸다. 목적지로 이동할 때까지 소비한 연료는 6이고, 이동하고 나서 12가 충전되므로 남은 연료의 양은 15이다. 이제 택시에서 각 손님까지의 최단거리는 둘 다 7이므로, 택시는 둘 중 행 번호가 더 작은 1번 승객의 출발지로 이동한다.
<그림 4> <그림 5> <그림 4>와 <그림 5>는 택시가 1번 승객을 태워 목적지로 이동시키는 경로를 나타낸다. 남은 연료의 양은 15 - 7 - 7 + 7×2 = 15이다.
<그림 6> <그림 7> <그림 6>과 <그림 7>은 택시가 3번 승객을 태워 목적지로 이동시키는 경로를 나타낸다. 최종적으로 남은 연료의 양은 15 - 5 - 4 + 4×2 = 14이다.
모든 승객을 성공적으로 데려다줄 수 있는지 알아내고, 데려다줄 수 있을 경우 최종적으로 남는 연료의 양을 출력하는 프로그램을 작성하시오.
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (추가 시간 없음) | 512 MB | 17355 | 3693 | 2189 | 19.487% |
입력
첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다.
다음 줄부터 N개의 줄에 걸쳐 백준이 활동할 영역의 지도가 주어진다. 0은 빈칸, 1은 벽을 나타낸다.
다음 줄에는 백준이 운전을 시작하는 칸의 행 번호와 열 번호가 주어진다. 행과 열 번호는 1 이상 N 이하의 자연수이고, 운전을 시작하는 칸은 빈칸이다.
그다음 줄부터 M개의 줄에 걸쳐 각 승객의 출발지의 행과 열 번호, 그리고 목적지의 행과 열 번호가 주어진다. 모든 출발지와 목적지는 빈칸이고, 모든 출발지는 서로 다르며, 각 손님의 출발지와 목적지는 다르다.
출력
모든 손님을 이동시키고 연료를 충전했을 때 남은 연료의 양을 출력한다. 단, 이동 도중에 연료가 바닥나서 다음 출발지나 목적지로 이동할 수 없으면 -1을 출력한다. 모든 손님을 이동시킬 수 없는 경우에도 -1을 출력한다.
풀이
- 택시의 위치로부터 거리별 손님을 찾는다. (BFS) 하나의 거리를 다 탐색했을 때 손님이 있다면 탐색을 종료한다.
- 손님의 위치로 이동할 연료가 있는지 거리와 비교하여 계산한다.
- 손님의 위치로부터 도착지까지 갈 수 있는지 확인한다.(BFS)
- 이동할 수 있다면 (연료 >= 거리) 현재 잔여 연료에 거리를 더해준다. (어차피 거리만큼 쓰고 그 2배만큼 충전하기 때문)
- 모든 과정에서 이동할 수 없다면 -1을 출력한다.
과정
손님을 찾는다.
static int findPassenger(Position pos) { Queue<Position> queue = new LinkedList<>(); PriorityQueue<Position> pq = new PriorityQueue<>(); // 손님을 담을 PQ for (int i = 1; i <= N; i++) { Arrays.fill(visited[i], false); } count = 0; // BFS에서 탐색중인 depth를 나타냄 (= 거리) queue.offer(pos); if (map[pos.r][pos.c] > 0) { // 현재 택시의 위치가 승객이 있는 자리 return map[pos.r][pos.c]; } int size = 0; while (!queue.isEmpty()) { count++; size = queue.size(); for (int step = 0; step < size; step++) { Position temp = queue.poll(); for (int i = 0; i < 4; i++) { int nr = temp.r + deltas[i][0]; int nc = temp.c + deltas[i][1]; if (isIn(nr, nc) && !visited[nr][nc] && map[nr][nc] >= 0) { if (map[nr][nc] > 0) { // 손님이면 pq에도 넣어준다. pq.offer(new Position(nr,nc)); } queue.offer(new Position(nr, nc)); visited[nr][nc] = true; } } } if(!pq.isEmpty()) { // 같은 거리의 탐색이 끝났다면 손님이 있었는지 확인한다. taxi = pq.poll(); // 택시의 위치를 손님의 위치로 바꿔준다. return map[taxi.r][taxi.c]; // 거리를 리턴한다. } } return -1; // 손님을 찾을 수 없다면 -1을 리턴한다. }
목적지까지 가 본다.
static int goDest(Position taxi, int passNo) { Queue<Position> queue = new LinkedList<>(); for (int i = 1; i <= N; i++) { Arrays.fill(visited[i], false); } queue.offer(taxi); visited[taxi.r][taxi.c] = true; int size = 0; count = 0; while (!queue.isEmpty()) { size = queue.size(); for (int step = 0; step < size; step++) { Position temp = queue.poll(); if (temp.r == destination[passNo].r && temp.c == destination[passNo].c) { return count; // 목적지에 도달했다면 거리를 리턴 } for (int i = 0; i < 4; i++) { int nr = temp.r + deltas[i][0]; int nc = temp.c + deltas[i][1]; if (isIn(nr, nc) && !visited[nr][nc] && map[nr][nc] >= 0) { queue.offer(new Position(nr, nc)); visited[nr][nc] = true; } } } count++; } return -1; // 도달할 수 없다면 -1 리턴 }
위 과정을 승객의 수 만큼 반복한다.
for (int i = 0; i < M; i++) { int passenger = findPassenger(taxi); // 승객을 찾고 승객의 번호 fuel -= count; // 거리만큼 빼 본다 if (passenger == -1 ||fuel <= 0) { // 승객이 없거나 연료를 다쓰면 종료. System.out.println(-1); return; } int use = goDest(taxi, passenger); // 목적지까지의 거리를 탐색 if (fuel < use || use == -1) { System.out.println(-1); return; } fuel += use; // 연료가 충분하다면 연료를 보충 map[taxi.r][taxi.c] = 0; // 맵에서 승객을 지워버림. taxi = destination[passenger]; // 택시의 위치를 도착지로 변경. } System.out.println(fuel);
최종 소스코드
import java.io.*;
import java.util.*;
public class Main {
static int N, M, fuel;
static int count = 0;
static int[][] map;
static boolean[][] visited;
static Position taxi;
static Position[] destination;
static int[][] deltas = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
static StringTokenizer st;
static class Position implements Comparable<Position> {
int r, c;
public Position(int r, int c) {
super();
this.r = r;
this.c = c;
}
@Override
public int compareTo(Position o) {
if (this.r == o.r) {
return this.c - o.c;
}
return this.r - o.r;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
fuel = Integer.parseInt(st.nextToken());
map = new int[N + 1][N + 1];
visited = new boolean[N + 1][N + 1];
destination = new Position[M + 1];
for (int i = 1; i <= N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 1; j <= N; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
map[i][j] = map[i][j] == 1 ? -1 : map[i][j];
}
}
st = new StringTokenizer(br.readLine());
taxi = new Position(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
for (int i = 1; i <= M; i++) {
st = new StringTokenizer(br.readLine());
int r = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
map[r][c] = i;
r = Integer.parseInt(st.nextToken());
c = Integer.parseInt(st.nextToken());
destination[i] = new Position(r, c);
}
for (int i = 0; i < M; i++) {
int passenger = findPassenger(taxi);
fuel -= count;
if (passenger == -1 ||fuel <= 0) {
System.out.println(-1);
return;
}
int use = goDest(taxi, passenger);
if (fuel < use || use == -1) {
System.out.println(-1);
return;
}
fuel += use;
map[taxi.r][taxi.c] = 0;
taxi = destination[passenger];
}
System.out.println(fuel);
}
static int findPassenger(Position pos) {
Queue<Position> queue = new LinkedList<>();
PriorityQueue<Position> pq = new PriorityQueue<>();
for (int i = 1; i <= N; i++) {
Arrays.fill(visited[i], false);
}
count = 0;
queue.offer(pos);
if (map[pos.r][pos.c] > 0) {
return map[pos.r][pos.c];
}
int size = 0;
while (!queue.isEmpty()) {
count++;
size = queue.size();
for (int step = 0; step < size; step++) {
Position temp = queue.poll();
for (int i = 0; i < 4; i++) {
int nr = temp.r + deltas[i][0];
int nc = temp.c + deltas[i][1];
if (isIn(nr, nc) && !visited[nr][nc] && map[nr][nc] >= 0) {
if (map[nr][nc] > 0) {
pq.offer(new Position(nr,nc));
}
queue.offer(new Position(nr, nc));
visited[nr][nc] = true;
}
}
}
if(!pq.isEmpty()) {
taxi = pq.poll();
return map[taxi.r][taxi.c];
}
}
return -1;
}
static int goDest(Position taxi, int passNo) {
Queue<Position> queue = new LinkedList<>();
for (int i = 1; i <= N; i++) {
Arrays.fill(visited[i], false);
}
queue.offer(taxi);
visited[taxi.r][taxi.c] = true;
int size = 0;
count = 0;
while (!queue.isEmpty()) {
size = queue.size();
for (int step = 0; step < size; step++) {
Position temp = queue.poll();
if (temp.r == destination[passNo].r && temp.c == destination[passNo].c) {
return count;
}
for (int i = 0; i < 4; i++) {
int nr = temp.r + deltas[i][0];
int nc = temp.c + deltas[i][1];
if (isIn(nr, nc) && !visited[nr][nc] && map[nr][nc] >= 0) {
queue.offer(new Position(nr, nc));
visited[nr][nc] = true;
}
}
}
count++;
}
return -1;
}
static boolean isIn(int r, int c) {
return r >= 1 && c >= 1 && r <= N && c <= N;
}
}
'Algorithm > BaekJoon' 카테고리의 다른 글
| [백준] 12919번 - A와 B 2 (java) (0) | 2022.01.12 |
|---|---|
| [백준] 22942번 - 데이터 체커 (java) (0) | 2022.01.08 |
| [백준] 1967번 - 트리의 지름 (java) (0) | 2022.01.05 |
| [백준] 15684 - 사다리 조작 (java) (0) | 2022.01.05 |
| [백준] 2573번 - 빙산 (java) (0) | 2021.12.31 |
