BOJ 19238 스타트 택시(Java)
문제 탐색하기
- 손님을 도착지로 데려다줄 때마다 연료가 충전되고, 연료가 바닥나면 그 날의 업무가 끝난다.
- 활동할 영역은 N×N 크기의 격자로 나타낼 수 있고, 각 칸은 비어 있거나 벽이 놓여 있다.
- 택시가 빈칸에 있을 때, 상하좌우로 인접한 빈칸 중 하나로 이동할 수 있으며 항상 최단 경로로 이동한다.
- M명의 승객을 태우는 것이 목표
- M명의 승객은 빈칸 중 하나에 서 있으며, 다른 빈칸 중 하나로 이동하려고 한다. 여러 승객이 같이 탑승하는 경우는 없다.
- 따라서 한 승객을 태워 목적지로 이동시키는 일을 M번 반복해야 한다.
- 태울 승객을 고를 때는 현재 위치에서 최단거리가 가장 짧은 승객을 고른다.
- 그런 승객이 여러 명이면 그중 행 번호가 가장 작은 승객을, 그런 승객도 여러 명이면 그중 열 번호가 가장 작은 승객을 고른다.
- 택시와 승객이 같은 위치에 서 있으면 그 승객까지의 최단거리는 0이다.
- 연료는 한 칸 이동할 때마다 1씩 소모된다.
- 승객을 목적지로 이동시키면 그 승객을 태워 이동하면서 소모한 연료의 양의 두 배가 충전된다.
- 이동하는 도중에 연료가 바닥나면 이동에 실패하고 그 날의 업무가 끝난다.
- 승객을 목적지로 이동시킨 후 연료가 바닥나는 경우는 실패한 것으로 간주하지 않는다.
모든 승객을 성공적으로 데려다줄 수 있는지 알아보고, 데려다줄 수 있을 경우 최종적으로 남는 연료의 양을 출력하는 프로그램을 작성하라.
입력
- 첫 줄에 N, M, 연료의 양이 주어진다.
- 다음 N개의 줄에 걸쳐 N×N 크기의 격자의 정보가 주어진다.
- 0은 빈칸, 1은 벽을 나타낸다.
- 벽이 있는 칸에는 승객이 서 있을 수 없다.
- 또, 벽이 있는 칸은 택시가 이동할 수 없다.
- 백준이 운전을 시작하는 칸의 행 번호와 열 번호가 주어진다.
- 행과 열 번호는 1 이상 N 이하의 자연수이고, 운전을 시작하는 칸은 빈칸이다.
- 다음 M개의 줄에 걸쳐 각 승객의 출발지의 행과 열 번호, 그리고 목적지의 행과 열 번호가 주어진다.
출력
- 모든 손님을 이동시키고 연료를 충전했을 때 남은 연료의 양을 출력한다.
- 이동 도중에 연료가 바닥나서 다음 출발지나 목적지로 이동할 수 없으면 -1을 출력한다.
- 모든 손님을 이동시킬 수 없는 경우에도 -1을 출력한다.
예제
# 입력
6 3 15
0 0 1 0 0 0
0 0 1 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 0 0
6 5
2 2 5 6
5 4 1 6
4 2 3 5
# 출력
14
코드 설계하기
구현 방법
- 승객 운송 과정
for (모든 승객을 태울 때까지) {
1. BFS로 가장 가까운 승객 찾기 (`findNearestPassenger`)
- 2차원 배열 passengerMap을 활용해 각 위치에 어떤 승객이 있는지 O(1)에 확인
- 한 번의 BFS로 모든 승객까지의 거리를 동시에 계산
- 최단 거리 우선 + 행 번호 작은 순 + 열 번호 작은 순으로 승객 선택
2. 승객을 태우고 연료 소모
- 선택된 승객까지의 거리만큼 연료 감소
3. BFS로 목적지까지 거리 계산 (`getDistance`)
- 승객의 출발지에서 목적지까지 최단 거리 계산
4. 목적지로 이동 및 연료 관리
- 목적지까지의 거리만큼 연료 감소
- 소모한 연료의 2배를 충전
5. 택시 위치 업데이트
- 택시 위치를 승객의 목적지로 갱신
6. 승객 완료 처리
- 해당 승객을 완료 상태로 표시
}
-
2차원 배열
passengerMap에 각 위치별로 어떤 승객이 있는지 미리 저장해, BFS 탐색 중 특정 위치에 도달했을 때 O(1) 시간에 승객 존재 여부를 확인할 수 있다. -
최단 거리의 승객을 모두 찾았다면 더 이상 탐색하지 않도록 하였다.
시간 복잡도
- N×N 격자에서 BFS 한 번의 시간 복잡도: O(N²)
- M명의 승객에 대해 각각 BFS 수행: O(M * N²)
- 이 과정을 M번 반복(모든 승객 처리): O(M² * N²)
- 총 시간 복잡도: O(M² * N²)
시도 회차 별 수정사항(Optional)
목적지 도착 후 연료가 정확히 0이 되는 경우를 고려하지 못했다…
정답 코드 (Java)
import java.io.*;
import java.util.*;
public class Main {
private static int N, M;
private static int fuel;
private static int[][] map;
private static int taxiRow, taxiCol;
private static Passenger[] passengers;
private static int[] dr = {-1, 1, 0, 0};
private static int[] dc = {0, 0, -1, 1};
private static class Passenger {
private int id;
private int startRow, startCol;
private int endRow, endCol;
private boolean completed;
public Passenger(int id, int startRow, int startCol, int endRow, int endCol) {
this.id = id;
this.startRow = startRow;
this.startCol = startCol;
this.endRow = endRow;
this.endCol = endCol;
this.completed = false;
}
}
private static class Point implements Comparable<Point> {
int row, col, dist;
public Point(int row, int col, int dist) {
this.row = row;
this.col = col;
this.dist = dist;
}
@Override
public int compareTo(Point o) {
if (this.dist != o.dist) {
return this.dist - o.dist;
}
if (this.row != o.row) {
return this.row - o.row;
}
return this.col - o.col;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer 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];
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());
}
}
st = new StringTokenizer(br.readLine());
taxiRow = Integer.parseInt(st.nextToken());
taxiCol = Integer.parseInt(st.nextToken());
passengers = new Passenger[M+1];
for (int i = 1; i <= M; i++) {
st = new StringTokenizer(br.readLine());
int startRow = Integer.parseInt(st.nextToken());
int startCol = Integer.parseInt(st.nextToken());
int endRow = Integer.parseInt(st.nextToken());
int endCol = Integer.parseInt(st.nextToken());
passengers[i] = new Passenger(i, startRow, startCol, endRow, endCol);
}
int completedCount = 0;
while (completedCount < M) {
// 가장 가까운 승객 찾기
int[] result = findNearestPassenger();
int nearestIndex = result[0];
int distance = result[1];
if (nearestIndex == -1 || distance > fuel) {
System.out.println(-1);
return;
}
// 연료 소비
fuel -= distance;
// 승객을 태운 후 목적지로 이동
Passenger p = passengers[nearestIndex];
int distToDest = getDistance(p.startRow, p.startCol, p.endRow, p.endCol);
if (distToDest == -1 || distToDest > fuel) {
System.out.println(-1);
return;
}
// 연료 소비 및 충전
fuel -= distToDest;
fuel += (distToDest * 2);
// 택시 위치 업데이트
taxiRow = p.endRow;
taxiCol = p.endCol;
// 승객 완료 처리
p.completed = true;
completedCount++;
}
System.out.println(fuel);
}
// BFS 한 번으로 모든 승객까지의 거리 계산
private static int[] findNearestPassenger() {
Queue<Point> queue = new LinkedList<>();
boolean[][] visited = new boolean[N+1][N+1];
PriorityQueue<Point> candidates = new PriorityQueue<>();
int[][] passengerMap = new int[N+1][N+1]; // 승객 인덱스 저장
// 승객 위치 맵 생성
for (int i = 1; i <= M; i++) {
Passenger p = passengers[i];
if (!p.completed) {
passengerMap[p.startRow][p.startCol] = i;
}
}
// 현재 택시 위치에 승객이 있는지 확인
if (passengerMap[taxiRow][taxiCol] > 0 && !passengers[passengerMap[taxiRow][taxiCol]].completed) {
taxiRow = passengers[passengerMap[taxiRow][taxiCol]].startRow;
taxiCol = passengers[passengerMap[taxiRow][taxiCol]].startCol;
return new int[]{passengerMap[taxiRow][taxiCol], 0};
}
queue.offer(new Point(taxiRow, taxiCol, 0));
visited[taxiRow][taxiCol] = true;
while (!queue.isEmpty()) {
Point curr = queue.poll();
// 현재 위치에 승객이 있는지 확인
if (passengerMap[curr.row][curr.col] > 0 && !passengers[passengerMap[curr.row][curr.col]].completed) {
candidates.offer(curr);
}
// 최단 거리의 승객을 모두 찾았다면 더 이상 탐색하지 않음
if (!candidates.isEmpty() && candidates.peek().dist < curr.dist) {
break;
}
for (int i = 0; i < 4; i++) {
int nr = curr.row + dr[i];
int nc = curr.col + dc[i];
if (nr < 1 || nr > N || nc < 1 || nc > N) continue;
if (map[nr][nc] == 1 || visited[nr][nc]) continue;
visited[nr][nc] = true;
queue.offer(new Point(nr, nc, curr.dist + 1));
}
}
if (candidates.isEmpty()) {
return new int[]{-1, -1}; // 승객을 찾을 수 없음
}
Point nearest = candidates.poll();
int nearestIndex = passengerMap[nearest.row][nearest.col];
// 택시 위치 업데이트
taxiRow = passengers[nearestIndex].startRow;
taxiCol = passengers[nearestIndex].startCol;
return new int[]{nearestIndex, nearest.dist};
}
// 목적지까지 거리 계산
private static int getDistance(int startRow, int startCol, int endRow, int endCol) {
if (startRow == endRow && startCol == endCol) return 0;
Queue<Point> queue = new LinkedList<>();
boolean[][] visited = new boolean[N+1][N+1];
queue.offer(new Point(startRow, startCol, 0));
visited[startRow][startCol] = true;
while (!queue.isEmpty()) {
Point curr = queue.poll();
for (int i = 0; i < 4; i++) {
int nr = curr.row + dr[i];
int nc = curr.col + dc[i];
if (nr < 1 || nr > N || nc < 1 || nc > N) continue;
if (map[nr][nc] == 1 || visited[nr][nc]) continue;
if (nr == endRow && nc == endCol) {
return curr.dist + 1;
}
visited[nr][nc] = true;
queue.offer(new Point(nr, nc, curr.dist + 1));
}
}
return -1; // 도달할 수 없는 경우
}
}
Leave a comment