![[백준 19238] 스타트 택시 (자바)](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FqIb0q%2FbtqNuP4hzqq%2FYcNNdZdo79Zy5Ur2ZwKkh1%2Fimg.png)
백준 19238번 스타트 택시 (자바)
출처
19238번: 스타트 택시
첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다
www.acmicpc.net
문제
스타트링크가 "스타트 택시"라는 이름의 택시 사업을 시작했다. 스타트 택시는 특이하게도 손님을 도착지로 데려다줄 때마다 연료가 충전되고, 연료가 바닥나면 그 날의 업무가 끝난다.
택시 기사 최백준은 오늘 M명의 승객을 태우는 것이 목표이다. 백준이 활동할 영역은 N×N 크기의 격자로 나타낼 수 있고, 각 칸은 비어 있거나 벽이 놓여 있다. 택시가 빈칸에 있을 때, 상하좌우로 인접한 빈칸 중 하나로 이동할 수 있다. 알고리즘 경력이 많은 백준은 특정 위치로 이동할 때 항상 최단경로로만 이동한다.
M명의 승객은 빈칸 중 하나에 서 있으며, 다른 빈칸 중 하나로 이동하려고 한다. 여러 승객이 같이 탑승하는 경우는 없다. 따라서 백준은 한 승객을 태워 목적지로 이동시키는 일을 M번 반복해야 한다. 각 승객은 스스로 움직이지 않으며, 출발지에서만 택시에 탈 수 있고, 목적지에서만 택시에서 내릴 수 있다.
백준이 태울 승객을 고를 때는 현재 위치에서 최단거리가 가장 짧은 승객을 고른다. 그런 승객이 여러 명이면 그중 행 번호가 가장 작은 승객을, 그런 승객도 여러 명이면 그중 열 번호가 가장 작은 승객을 고른다. 택시와 승객이 같은 위치에 서 있으면 그 승객까지의 최단거리는 0이다. 연료는 한 칸 이동할 때마다 1만큼 소모된다. 한 승객을 목적지로 성공적으로 이동시키면, 그 승객을 태워 이동하면서 소모한 연료 양의 두 배가 충전된다. 이동하는 도중에 연료가 바닥나면 이동에 실패하고, 그 날의 업무가 끝난다. 승객을 목적지로 이동시킨 동시에 연료가 바닥나는 경우는 실패한 것으로 간주하지 않는다.
<그림 1>
<그림 1>은 택시가 활동할 영역의 지도를 나타내며, 택시와 세 명의 승객의 출발지와 목적지가 표시되어 있다. 택시의 현재 연료 양은 15이다. 현재 택시에서 각 손님까지의 최단거리는 각각 9, 6, 7이므로, 택시는 2번 승객의 출발지로 이동한다.
<그림 2>는 택시가 2번 승객의 출발지로 가는 경로를, <그림 3>은 2번 승객의 출발지에서 목적지로 가는 경로를 나타낸다. 목적지로 이동할 때까지 소비한 연료는 6이고, 이동하고 나서 12가 충전되므로 남은 연료의 양은 15이다. 이제 택시에서 각 손님까지의 최단거리는 둘 다 7이므로, 택시는 둘 중 행 번호가 더 작은 1번 승객의 출발지로 이동한다.
<그림 4>와 <그림 5>는 택시가 1번 승객을 태워 목적지로 이동시키는 경로를 나타낸다. 남은 연료의 양은 15 - 7 - 7 + 7×2 = 15이다.
<그림 6>과 <그림 7>은 택시가 3번 승객을 태워 목적지로 이동시키는 경로를 나타낸다. 최종적으로 남은 연료의 양은 15 - 5 - 4 + 4×2 = 14이다.
모든 승객을 성공적으로 데려다줄 수 있는지 알아내고, 데려다줄 수 있을 경우 최종적으로 남는 연료의 양을 출력하는 프로그램을 작성하시오.
입력
첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다.
다음 줄부터 N개의 줄에 걸쳐 백준이 활동할 영역의 지도가 주어진다. 0은 빈칸, 1은 벽을 나타낸다.
다음 줄에는 백준이 운전을 시작하는 칸의 행 번호와 열 번호가 주어진다. 행과 열 번호는 1 이상 N 이하의 자연수이고, 운전을 시작하는 칸은 빈칸이다.
그다음 줄부터 M개의 줄에 걸쳐 각 승객의 출발지의 행과 열 번호, 그리고 목적지의 행과 열 번호가 주어진다. 모든 출발지와 목적지는 빈칸이고, 모든 출발지는 서로 다르며, 각 손님의 출발지와 목적지는 다르다.
출력
모든 손님을 이동시키고 연료를 충전했을 때 남은 연료의 양을 출력한다. 단, 이동 도중에 연료가 바닥나서 다음 출발지나 목적지로 이동할 수 없으면 -1을 출력한다. 모든 손님을 이동시킬 수 없는 경우에도 -1을 출력한다.
입출력 예
접근 방법
이 문제는 주어진 조건 외에 생각할 조건이 많아서 너무 힘들었다. 3일동안 맞왜틀 시전ㅎㅎ
아래는 문제에서 주어진 조건 이외에 생각할 조건이다.
1. 도착지에 태울 승객이 있는 경우(태우러 이동할 필요 X)
2. 동일한 목적지를 가지고 있는 승객이 존재하는 경우(목적지를 배열에 담아서 비교 불가능)
1. 벽, 태울 승객을 담을 배열(map)과 시간을 담을 배열(time) 방문을 담을 배열(visit), 택시 위치와 최소 위치, 도착지를 담을 hashmap을 생성한다.
2. 승객과 벽의 숫자가 겹칠 수 있으므로 벽은 주어진 범위에 넘어가는 401로 변경한다.
3. 승객 위치는 map에 넣어주고, 목적지는 destination에 넣어준다.
4. 승객 개수만큼 for문을 돌려 승객을 찾고 이동한 후 목적지까지 데려다준다.
- 최소 행, 열, 거리 변수는 최댓값으로 초기화한다. 방문 배열과 시간 배열도 초기화한 이후에 최소거리에 있는 승객을 찾는다. (bfs)
- 현재 위치에 손님이 있는 경우가 있을 수 있으므로 예외처리를 해준다.
- bfs로 탐색 중 동일한 위치의 승객을 만날 시 낮은 행을. 동일한 행의 승객이 여러 명인 경우 낮은 열에 있는 승객을 태운다.
(이때, 승객의 번호를(man) 담아 목적지 찾는데 사용할 수 있도록 한다.)
- 최소 행, 열이 초기값과 다르면 손님을 찾은 것이므로 택시의 위치를 변경하고, 연료를 움직인 만큼 감소시킨다.
- 승객을 찾지 못하면 -1을 반환한다.
- 이후, 손님을 목적지까지 배달한다.(delievery)
- bfs로 탐색하다가 hashmap에서 목적이 위치를 가져와 도달하면 연산을 끝낸다.
- 도착지 가는 도중 연료가 떨어진 경우 -1을 반환한다. 무사히 도착했으면 이동 거리만큼 연료를 감소한 후, 이동 거리*2를 더해준다.
- 택시 위치를 변경시켜준다.
- 배달지를 찾지 못하면 -1을 반환한다.
내 코드
package dfsbfs;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class StartTaxi2 {
private static int n, m, fuel;
private static int[][] map; //벽&태울승객
private static int[][] time; //시간&연료
private static boolean[][] visit; //방문
private static int minX, minY, minD; //x,y,연료
private static int taxiX, taxiY; //택시위치
private static int man; //승객
private static int[] dx = { -1, 0, 1, 0 };
private static int[] dy = { 0, 1, 0, -1 };
//승객들의 도착지
private static HashMap<Integer, Taxi> destination = new HashMap<Integer, Taxi>();
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(reader.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
fuel = Integer.parseInt(st.nextToken());
map = new int[n + 1][n + 1];
time = new int[n + 1][n + 1];
visit = new boolean[n + 1][n + 1];
for (int i = 1; i <= n; i++) {
st = new StringTokenizer(reader.readLine());
for (int j = 1; j <= n; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
if (map[i][j] == 1)
map[i][j] = 401;// 벽
}
}
String[] input = reader.readLine().split(" ");
taxiX = Integer.parseInt(input[0]);
taxiY = Integer.parseInt(input[1]);
for (int i = 1; i <= m; i++) {
st = new StringTokenizer(reader.readLine());
int startX = Integer.parseInt(st.nextToken());
int startY = Integer.parseInt(st.nextToken());
int departX = Integer.parseInt(st.nextToken());
int departY = Integer.parseInt(st.nextToken());
map[startX][startY] = i; // 승객 위치
destination.put(i, new Taxi(departX, departY)); // 목적지 위치
}
man = 0;
for (int i=1; i<=m; i++) {
minX = minY = minD = Integer.MAX_VALUE;
//방문 초기화
visit = new boolean[n + 1][n + 1];
//시간 초기화
for (int j=1; j<=n; j++) {
for (int k=1; k<=n; k++) {
time[j][k] = -1;
}
}
//가까운 손님 찾기
bfs();
if (minX != Integer.MAX_VALUE && minY != Integer.MAX_VALUE) {
fuel -= minD;// 손님 태우러 이동(연료 소모)
//손님 찾아가다 연료 떨어진 경우
if (fuel < 0) {
fuel = -1;
break;
}
// 손님 위치로 갱신
taxiX = minX;
taxiY = minY;
//시간 초기화
for (int j = 1; j <= n; j++) {
for (int k = 1; k <= n; k++) {
time[j][k] = -1;
}
}
visit = new boolean[n + 1][n + 1];
//손님 목적지 배달
//목적지 도달했을 때
if (delivery()) {
if (fuel < 0) {
fuel = -1;
break;
}
fuel += 2*minD;//연료 2배 충전
//손님 내려다준 곳으로 위치 변경
taxiX = minX;
taxiY = minY;
} else {
//목적지 도달 실패했을 때
fuel = -1;
break;
}
} else {
//가까운 승객을 찾을 수 없을 때
fuel = -1;
break;
}//if
}//for
System.out.println(fuel);
}
private static boolean delivery() {
//승객의(man) 목적지 추출
int x = destination.get(man).x;
int y = destination.get(man).y;
Queue<Taxi> q = new LinkedList<Taxi>();
q.add(new Taxi(taxiX, taxiY));
time[taxiX][taxiY] = 0;
map[taxiX][taxiY] = 0;
visit[taxiX][taxiY] = true;
//man이 목적지
while (!q.isEmpty()) {
Taxi taxi = q.remove();
int qx = taxi.x;
int qy = taxi.y;
//목적지로 도착했을 때
if (qx == x && qy == y) {
//택시 위치 이동
minX = qx;
minY = qy;
minD = time[qx][qy];
fuel -= minD; //연료 감소
destination.remove(man);
return true;
}
for (int i=0; i<dx.length; i++) {
int nx = qx + dx[i];
int ny = qy + dy[i];
if (nx < 1 || ny < 1 || nx > n || ny > n || map[nx][ny] == 401) {
continue;
}
if (!visit[nx][ny] && (map[nx][ny] >= 0 && map[nx][ny] < 401)) {
visit[nx][ny] = true;
time[nx][ny] = time[qx][qy] + 1;
q.add(new Taxi(nx, ny));
}
}//for
}//while
return false;
}
private static void bfs() {
//현재 위치에 태울 승객 있는 경우
if (map[taxiX][taxiY] > 0 && map[taxiX][taxiY] < 401) {
minX = taxiX;
minY = taxiY;
minD = 0;
man = map[taxiX][taxiY];
return;
}
Queue<Taxi> q = new LinkedList<Taxi>();
q.add(new Taxi(taxiX, taxiY));
time[taxiX][taxiY] = 0;
visit[taxiX][taxiY] = true;
while (!q.isEmpty()) {
Taxi taxi = q.remove();
int qx = taxi.x;
int qy = taxi.y;
for (int i=0; i<dx.length; i++) {
int nx = qx + dx[i];
int ny = qy + dy[i];
if (nx < 1 || ny < 1 || nx > n || ny > n || map[nx][ny] == 401) {
continue;
}
time[nx][ny] = time[qx][qy] + 1;
if (map[nx][ny] < 401 && map[nx][ny] > 0) {
if (time[nx][ny] < minD) {
//처음 방문 or 더 가까운곳
minX = nx;
minY = ny;
minD = time[nx][ny];
man = map[nx][ny];
} else if (time[nx][ny] == minD) {
//가까운곳 여러번 방문시
if (nx < minX) {
//더 낮은 행으로
minX = nx;
minY = ny;
man = map[nx][ny];
} else if (nx == minX) {
//낮은 행이 여러개일 때
if (ny < minY) {
minX = nx;
minY = ny;
man = map[nx][ny];
}
}
}
}//if
if (!visit[nx][ny]) {
visit[nx][ny] = true;
q.add(new Taxi(nx, ny));
}
}//for
}//while
}//bfs
}
class Taxi {
int x, y;
public Taxi(int x, int y) {
this.x = x;
this.y = y;
}
}
고려할 점
1. 문제의 조건대로 승객을 찾을 것
2. 추가로 고민할 경우를 고려할 것
'알고리즘 > 백준' 카테고리의 다른 글
| [백준 11726] 2xn 타일링 2 (자바) (0) | 2020.11.22 |
|---|---|
| [백준 11726] 2xn 타일링 (자바) (0) | 2020.11.22 |
| [백준 17143] 낚시왕 (자바) (0) | 2020.11.14 |
| [백준 16296] 배열 돌리기 1 (자바) (0) | 2020.11.14 |
| [백준 16236] 아기 상어 (자바) (0) | 2020.11.14 |