https://www.acmicpc.net/problem/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이다.
모든 승객을 성공적으로 데려다줄 수 있는지 알아내고, 데려다줄 수 있을 경우 최종적으로 남는 연료의 양을 출력하는 프로그램을 작성하시오.
입력
첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다.
다음 줄부터 N개의 줄에 걸쳐 백준이 활동할 영역의 지도가 주어진다. 0은 빈칸, 1은 벽을 나타낸다.
다음 줄에는 백준이 운전을 시작하는 칸의 행 번호와 열 번호가 주어진다. 행과 열 번호는 1 이상 N 이하의 자연수이고, 운전을 시작하는 칸은 빈칸이다.
그다음 줄부터 M개의 줄에 걸쳐 각 승객의 출발지의 행과 열 번호, 그리고 목적지의 행과 열 번호가 주어진다. 모든 출발지와 목적지는 빈칸이고, 모든 출발지는 서로 다르며, 각 손님의 출발지와 목적지는 다르다.
출력
모든 손님을 이동시키고 연료를 충전했을 때 남은 연료의 양을 출력한다. 단, 이동 도중에 연료가 바닥나서 다음 출발지나 목적지로 이동할 수 없으면 -1을 출력한다. 모든 손님을 이동시킬 수 없는 경우에도 -1을 출력한다.
풀이 코드를 넣고, 이후 설명을 하겠다.
import java.util.*;
import java.io.*;
public class 스타트택시 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st =new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int Y = Integer.parseInt(st.nextToken());
int[][] arr = new int[N][N];
for(int i = 0; i<N;i++) {
st = new StringTokenizer(br.readLine());
for(int j = 0; j<N;j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
st =new StringTokenizer(br.readLine());
int R = Integer.parseInt(st.nextToken())-1;
int C = Integer.parseInt(st.nextToken())-1;
int[] dr = new int[M+2];
int[] dc = new int[M+2];
int [] dy = new int[M+2];
for(int i = 0; i<M+2;i++) {
dy[i] = Integer.MAX_VALUE;
}
for(int i = 0; i<M;i++) {
st = new StringTokenizer(br.readLine());
int r = Integer.parseInt(st.nextToken())-1;
int c = Integer.parseInt(st.nextToken())-1;
dr[i+2]= Integer.parseInt(st.nextToken())-1;
dc[i+2] = Integer.parseInt(st.nextToken())-1;
arr[r][c] = i+2;
Queue<int[]> q = new LinkedList<int[]>();
q.add(new int[] {r,c,0});
boolean[][] v = new boolean[N][N];
v[r][c] =true;
while(!q.isEmpty()) {
int[] t = q.poll();
//System.out.println(Arrays.toString(t));
r = t[0];c = t[1];int y = t[2];
if(dr[i+2]==r && dc[i+2]==c) {
dy[i+2]= y;
break;
}
y++;
if(r>0 && arr[r-1][c]!=1 && !v[r-1][c]) {q.add(new int[]{r-1,c,y});v[r-1][c]=true;}
if(c>0 && arr[r][c-1]!=1 && !v[r][c-1]) {q.add(new int[] {r,c-1,y});v[r][c-1]=true;}
if(c<N-1 && arr[r][c+1]!=1 && !v[r][c+1]) {q.add(new int[] {r,c+1,y});v[r][c+1]=true;}
if(r<N-1 && arr[r+1][c]!=1 && !v[r+1][c]) {q.add(new int[] {r+1,c,y});v[r+1][c]=true;}
}
}
PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
if(o1[2]==o2[2]) {
if(o1[0]==o2[0])return o1[1]-o2[1];
return o1[0]-o2[0];
}
return o2[2]-o1[2];
}
}) ;
pq.add(new int[] {R,C,Y});
boolean [][] v = new boolean[N][N];
v[R][C]= true;
while(!pq.isEmpty()) {
int r = pq.peek()[0];
int c = pq.peek()[1];
int y = pq.poll()[2];
//System.out.println(r + " " + c + " "+y);
if(arr[r][c]>1) {
int i = arr[r][c];
if(y<dy[i]) {
System.out.print(-1);
System.exit(0);
}
pq.clear();
v = new boolean[N][N];
v[dr[i]][dc[i]] = true;
pq.add(new int[] {dr[i],dc[i],y+dy[i]});
arr[r][c] = 0;
if(--M==0) {
Y =y+dy[i];
break;
}
}
else {
y--;
if(r>0 && arr[r-1][c]!=1 && !v[r-1][c]) {pq.add(new int[]{r-1,c,y});v[r-1][c]=true;}
if(c>0 && arr[r][c-1]!=1 && !v[r][c-1]) {pq.add(new int[] {r,c-1,y});v[r][c-1]=true;}
if(c<N-1 && arr[r][c+1]!=1 && !v[r][c+1]) {pq.add(new int[] {r,c+1,y});v[r][c+1]=true;}
if(r<N-1 && arr[r+1][c]!=1 && !v[r+1][c]) {pq.add(new int[] {r+1,c,y});v[r+1][c]=true;}
}
}
if(M!=0)System.out.println(-1);
else System.out.println(Y);
//83%에서 틀렸다고 뜬다..-> 해결!
}
}
총 줄바꿈을 전부 한게 아니더라도 길고 긴 코드이다...
여기서 사용하는 알고리즘을 하나씩 뽑아서 구현하여야하는데, 먼저 이 문제 설명을 읽고 파악한 것은
최단 거리를 찾아서 택시가 이동한다는 점이다. 이 부분이 이 알고리즘이 해결하는 핵심이다.
여기에서 최단 거리를 찾는 방법은 BFS(넓이우선탐색)을 진행한다.
여기에서 두가지 방법으로 탐색이 진행되는데,
1. 택시가 최단거리 승객 탐색(같은 거리라면 행렬순 )
2. 승객이 목적지로 최단거리 이동( 이부분이 83%에서 틀리게한 주범이었다.)
이 발생한다.
이를 구현하고자, 우선 2를 먼저 구현하였다.
미리 최단 거리를 계산해 두고, 사실 이동과정과 목적지는 이후로 필요 없으니, 목적지까지 소요되는 비용이 중요하게 이용된다.
int[] dr 은 목적지의 행 , dc는 목적지의 열, 그리고 dy는 목적지까지 소요되는 연료이다.
이를 해결하기 위해서
bfs로 최단거리를 탐색해 나가면서, 가장 연료를 적게 쓰면서 목적지를 찾는 방법을 탐색한다.
위 bfs는 비슷하게 이후 택시가 최단거리를 찾는 경우에도 복사해서 사용하여 편리하였다.
여기서 중요한 점이
승객이 목적지 까지 갈 수 없는 방법도 있다는 점이다. 그런 경우 최대값을 목적지에 넣어 주었다. (진짜 이거 찾아낸 나 너무 칭찬해ㅠㅠㅠ 몰랐으면 포기할 뻔 했다ㅠㅠㅠ)
여기서 추가 설명으로 데이터를 받을 떄 M+2의 배열로 선언한 이유는 arr지도로 확인을 하면서 가기 위하여 승객을 2~M+2까지의 승객을 숫자로 넣어 주었기 때문이다.
이후 이러한 값을 먼저 가지고 가면 승객 (arr[r][c]>=2)을 찾은 경우 바로 연료에서 dy[arr[r][c]]를 더하는 방식으로 해결할 수 있다.
이후 택시의 시작점부터 최단 거리에 있는 승객을 PriorityQueue로 탐색하면서 진행한다.
PriorityQueue를 사용하여야 행과 열에 따라 승객을 선택할 수 있게 된다.
Queue에는 현재 r의 값(행 위치) , (열 위치) c, y(현재 남은 연료) 가 저장된다.
연료가 많다는 것은 가까이 있다는 것을 의미하므로 y(역순: o1[2]), r(o1[0]), c(o1[1])식으로 정렬이 된다.
이후 승객의 목적지를 찾는 방식과 동일하게 Queue로 BFS를 돌면서 탐색하게 된다.
이떄 앞선 승객이 목적지 까지 가는 방식을 가지고 있기 때문에, arr[r][c]>=2인 승객의 위치를 확인 하였을 경우
만약 목적지까지 갈 연료가 없다면, -1을 출력하고, 프로그램을 끝낸다.
아니라면 ,이전에 담겨져 있던 값과, 방문 확인을 초기화 하고, pq에 승객을 태우고 도착할 목적지, 그리고 목적지에서 충전되는 연료를 합쳐 pq에 넣어주게된다.
이 과정에서 모든 승객을 태웠는지 확인하기 위하여 앞서 받아온 M에서 1씩을 뺴주면서 검사를 하게 되는데, 승객이 0일 경우, 처음에 남은 연료로 사용했던 Y변수에 y+dy[i]인 연료 양을 넣고, 루프를 빠져나오게 된다. ( 사실 바로 출력하고 프로그램을 끝내도 된다. )
만약 이 과정 없이 loop가 끝났다면,택시가 승객을 태울 수 없는 경우이기 때문에, M의 값을 다시 검사해 결과를 출력한다.
이중 BFS를 두번 사용하는 것이 이 문제 해결의 핵심이라고 할 수 있겠다.
'코딩테스트 연습 > 백준' 카테고리의 다른 글
| [ 백준 / 13460 ] Gold 2 구슬탈출2 : JAVA (0) | 2020.07.20 |
|---|---|
| [ 백준 / 17406 ] 배열돌리기4 - java (0) | 2020.07.09 |
| [ 백준 17281번 ] Gold IV - ⚾ ( 야구) - 자바 (0) | 2020.07.04 |
| [ 백준 / 14503번 ] Gold V - 로봇 청소기 - 자바 ( java) (0) | 2020.06.23 |
| [백준] 16234번 인구 이동 - java (0) | 2020.04.24 |
