알고리즘/BOJ
BJ G4 19238 스타트택시
- -
BJ G4 19238 스타트택시
문제링크
http://www.acmicpc.net/problem/19238
19238번: 스타트 택시
첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다
www.acmicpc.net
* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.
핵심 컨셉
고려사항
-
M 명의 손님을 목적지로 이동시킴 따라서 M 번 손님 선택 --> 목적지 이동을 반복
-
손님 선택 기준: 1. 가장 가까운 위치의 손님 2. 1이 같다면 행 번호가 가장 작은 손님, 2도 같다면 열 번호가 가장 작은 손님
-
1칸을 이동할 때마다 연료는 1씩 감소, 연료의 양이 0이 되면 이동 중지
-
손님을 이동시킨 후는 자리를 0으로 만들어줄 것
-
도착지에서 즉시 손님을 태울 수 있음
입력사항
-
지도의 크기: N×N (2 ≤ N ≤ 20) 지도에서 0은 빈칸, 1은 벽
-
1 ≤ 초기 연료 ≤ 500,000 이며 연료통은 무한
-
손님을 태운 후 이동한 거리의 두 배가 충전됨(손님을 태우러 갈때는 빼고)
-
승객 수 M 1 ≤ M ≤ N^2
출력사항
-
모든 손님을 이동시키고 충전했을 때 남은 연료의 양 출력
-
손님이 남아있다면 -1 출력
동영상 설명
1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.
소스보기
동영상 설명을 보고도 전혀 구현이 안된다면 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.
꼭 작성할 각오가 되어있습니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
public class BJ_G4_19238_스타트택시 {
static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
static int N, M, K;
static int[][] map;
static Point[] dests;
static int startR, startC;
static int[][] dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
public static void main(String[] args) throws IOException {
input = new BufferedReader(new StringReader(src));
StringTokenizer tokens = new StringTokenizer(input.readLine());
// 지도의 index들이 1부터 시작
N = Integer.parseInt(tokens.nextToken()) + 1; // 지도 크기
M = Integer.parseInt(tokens.nextToken()); // 고객 수
K = Integer.parseInt(tokens.nextToken()); // 연료 량
map = new int[N][N];
for (int r = 1; r < N; r++) {
tokens = new StringTokenizer(input.readLine());
for (int c = 1; c < N; c++) {
map[r][c] = Integer.parseInt(tokens.nextToken());
}
}
tokens = new StringTokenizer(input.readLine());
startR = Integer.parseInt(tokens.nextToken());
startC = Integer.parseInt(tokens.nextToken());
// 목적지 정보
dests = new Point[M + 2];
// 0과 1은 이미 사용 중이므로 고객은 2번부터로 표시
for (int i = 2; i < M + 2; i++) {
tokens = new StringTokenizer(input.readLine());
// 앞에 두 개의 정보인 손님은 지도에 표시하고
map[Integer.parseInt(tokens.nextToken())][Integer.parseInt(tokens.nextToken())] = i;
// 뒤에 두 개의 정보인 목적지는 별도의 배열에 저장
dests[i] = new Point(Integer.parseInt(tokens.nextToken()), Integer.parseInt(tokens.nextToken()));
}
/*for (int[] row : map) {
System.out.println(Arrays.toString(row));
}*/
boolean fail = false;
// M 명의 고객을 처리하면 된다. 중간에 실패하면 가볼 필요 없다.
for (int m = 0; m < M; m++) {
Taxi taxi = findPassenger();
// m 번 내에 손님을 못찾으면 실패
if (taxi == null) {
fail = true;
break;
}
// 손님 태운 위치는 공백으로 수정
map[taxi.row][taxi.col] = 0;
// System.out.println(m + "번째 손님 탑승: " + taxi);
taxi = toDest(taxi);
if (taxi == null) {
fail = true;
break;
}
// System.out.println(m + "번째 손님 하차: " + taxi);
}
System.out.println(fail ? -1 : K);
}
static Taxi findPassenger() {
// 현재 위치가 출발점인 경우
if (map[startR][startC] > 1) {
return new Taxi(startR, startC, K, map[startR][startC]);
}
PriorityQueue<Taxi> pq = new PriorityQueue<>();
Queue<Taxi> q = new LinkedList<>();
boolean[][] visited = new boolean[N][N];
Taxi st = new Taxi(startR, startC, K, 0);
q.offer(st);
visited[startR][startC] = true;
while (!q.isEmpty()) {
int size = q.size();
while (size-- > 0) {
Taxi front = q.poll();
// 택시에 연료가 없다면 땡!!
if (front.fuel == 0) {
return null;
}
for (int d = 0; d < 4; d++) {
int nr = front.row + dirs[d][0];
int nc = front.col + dirs[d][1];
if (isIn(nr, nc) && !visited[nr][nc] && map[nr][nc] != 1) {
visited[nr][nc] = true;
if (map[nr][nc] > 1) {
pq.offer(new Taxi(nr, nc, front.fuel - 1, map[nr][nc]));
} else {
q.offer(new Taxi(nr, nc, front.fuel - 1, 0));
}
}
}
}
if (pq.size() > 0) {
return pq.poll();
}
}
return null;
}
static Taxi toDest(Taxi taxi) {
// 손님의 목적지까지 가기 전에 기본 연료 량
int baseFuel = taxi.fuel;
Point target = dests[taxi.passNo];
// System.out.println("목적지 출발: " + taxi + ",목적지: " + target);
Queue<Taxi> q = new LinkedList<>();
q.offer(taxi);
boolean[][] visited = new boolean[N][N];
visited[taxi.row][taxi.col] = true;
while (!q.isEmpty()) {
Taxi front = q.poll();
if (front.fuel == 0) {
return null;
}
for (int d = 0; d < dirs.length; d++) {
int nr = front.row + dirs[d][0];
int nc = front.col + dirs[d][1];
if (isIn(nr, nc) && !visited[nr][nc] && map[nr][nc] != 1) {
visited[nr][nc] = true;
Taxi nextTaxi = new Taxi(nr, nc, front.fuel - 1, front.passNo);
if (nr == target.row && nc == target.col) {
// 좌표 처리 하고
startR = nr;
startC = nc;
// 기름 정산
K = nextTaxi.fuel + (baseFuel - nextTaxi.fuel) * 2;
// System.out.println("정산 정보: 남은 기름:" + K);
return nextTaxi;
}
q.offer(nextTaxi);
}
}
}
return null;
}
static boolean isIn(int r, int c) {
return 1 <= r && r < N && 1 <= c && c < N;
}
static class Point {
int row, col;
public Point(int row, int col) {
this.row = row;
this.col = col;
}
@Override
public String toString() {
return "[row=" + row + ", col=" + col + "]";
}
}
static class Taxi implements Comparable<Taxi> {
int row, col;
int fuel;
int passNo;
public Taxi(int row, int col, int fuel, int passNo) {
this.row = row;
this.col = col;
this.fuel = fuel;
this.passNo = passNo;
}
@Override
public int compareTo(Taxi o) {
// 거리가 같다면 row가 작은 녀석
if (this.fuel == o.fuel) {
// row가 같다면 col이 작은 녀석
if (this.row == o.row) {
return Integer.compare(this.col, o.col);
} else {
return Integer.compare(this.row, o.row);
}
}
// 가까운 위치의 녀석이니까 내림차순
else {
return Integer.compare(o.fuel, this.fuel);
}
}
@Override
public String toString() {
return "[(" + row + "," + col + "), fuel=" + fuel + ", passNo=" + passNo + "]";
}
}
private static String src = "6 4 14\r\n" +
"0 0 1 0 0 0\r\n" +
"0 0 1 0 0 0\r\n" +
"0 0 0 0 0 0\r\n" +
"0 0 0 0 0 0\r\n" +
"0 0 0 0 1 0\r\n" +
"0 0 0 1 0 0\r\n" +
"6 5\r\n" +
"2 2 5 6\r\n" +
"5 4 1 6\r\n" +
"4 2 3 5\r\n" +
"1 6 5 4";
}
소중한 공감 감사합니다