문제
스타트링크가 "스타트 택시"라는 이름의 택시 사업을 시작했다. 스타트 택시는 특이하게도 손님을 도착지로 데려다줄 때마다 연료가 충전되고, 연료가 바닥나면 그 날의 업무가 끝난다.
택시 기사 최백준은 오늘 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을 출력한다.
예제 입력 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 1 0
0 0 0 1 0 0
6 5
2 2 5 6
5 4 1 6
4 2 3 5
예제 출력 1 복사
14
package Samsung;
import java.util.*;
import java.io.*;
public class 스타트택시 {
static int n,m,k;
static int[][] map;
static int cx,cy;
static Ctmr[] carr;
static int rk;
static int[] dx = {-1,1,0,0};
static int[] dy = {0,0,-1,1};
static class Ctmr{
int sx ,sy,ex,ey;
Ctmr(int sx, int sy , int ex , int ey){
this.sx = sx;
this.sy = sy;
this.ex = ex;
this.ey = ey;
}
}
static class Pair {
int x, y;
Pair(int x , int y){
this.x =x;
this.y =y;
}
}
static class Info implements Comparable<Info>{
int x;
int y;
int num;
int dist;
Info(int num, int dist, int x,int y){
this.num = num;
this.dist =dist;
this.x =x;
this.y =y;
}
@Override
public int compareTo(Info o) {
if(this.dist==o.dist) {
if(this.x==o.x) {
return this.y-o.y;
}
return this.x-o.x;
}
return this.dist-o.dist;
}
}
public static void print() {
System.out.println("car:"+cx+","+cy);
for(int i=0; i<carr.length; i++) {
if(carr[i]!=null) {
System.out.println(i+":"+carr[i].sx+","+carr[i].sy);
}
}
}
public static boolean cango(int x, int y) {
return x>=0 && x<n && y>=0 && y<n;
}
static boolean[][] check;
/*어려웠던점1: 일단 모든 승객을 한번의 bfs로 탐색 후 priority queue 에 넣어서 가장 가까운 승객을 찾아준다.=> 시간초과 해결 방법*/
/*현재 지점에서 가장 가까운 사람을 찾기 위한 bfs*/
public static void bfs(Pair s, PriorityQueue<Info> pq) {
check = new boolean[n][n];
Queue<Pair> q = new LinkedList<>();
q.add(new Pair(s.x,s.y));
check[s.x][s.y]=true;
int dist=0;
if(map[s.x][s.y]!=-1 && map[s.x][s.y]!=0) { //출발지점과 목적지점이 같을 경우 pq 에 넣어줘야함 /*어려웠던점2*/
pq.add(new Info(map[s.x][s.y],dist,s.x,s.y));
}
while(!q.isEmpty()) {
int sz = q.size();
if(dist>=rk) {break;} //rk 를 넘어가면 더이상 사람을 태울 수 없게 된다.
for(int i=0; i<sz; i++) {
Pair p = q.poll();
for(int t=0; t<4; t++) {
int nx = p.x + dx[t];
int ny = p.y +dy[t];
if(cango(nx,ny) && map[nx][ny]!=-1 && check[nx][ny]==false) {
check[nx][ny]=true;
q.add(new Pair(nx,ny));
if(map[nx][ny]!=0) { //현재 해당 부분이 사람이 있는 곳이라면
pq.add(new Info(map[nx][ny],dist+1,nx,ny)); // 그사람의대한 정보를 pq에 넣어준다.
}
}
}
}
dist++;
}
}
/*현재 태운 사람을 목적지로 향하는데 가는 거리를 구해준다.*/
public static int bfs2(Pair s, Pair e) {
check = new boolean[n][n];
if(s.x==e.x && s.y==e.y) {return 0;} //출발지점과 목적지점이 같을 경우 바로 0을 반환 /*어려웠던점2*/
Queue<Pair> q = new LinkedList<>();
q.add(new Pair(s.x,s.y));
check[s.x][s.y]=true; //방문 여부를 알려주는 check 배열
boolean tg = false; //목적지에 도달했는지 알려주는 토글 버튼
int dist=0;
while(!q.isEmpty()) {
int sz = q.size(); //같은 depth 끼리 탐색하기 위한 sz설정
if(dist>=rk) {break;} // 가는 거리가 연료를 넘어서게 되면 탐색을 중단한다
for(int i=0; i<sz; i++) {
Pair p = q.poll();
for(int t=0; t<4; t++) { //4방향 탐색
int nx = p.x + dx[t];
int ny = p.y +dy[t];
if(cango(nx,ny) && map[nx][ny]!=-1 && check[nx][ny]==false) { //벽이아니고 지난 적 이 없다면
if(nx == e.x && ny== e.y) {//목적지에 도달을 했다.
tg=true; break; //목적지 도달 토글 true로 만듬
}
check[nx][ny]=true; //방문 여부를 알려주는 check 배열
q.add(new Pair(nx,ny));
}
}
if(tg)break; //목적지 도달 했으니까 break
}
dist++;
if(tg)break; //목적지 도달 했으니까 break
}
if(!tg)dist=-1; //목적지에 도달하지 않고 탐색이 끝나거나, 가는 도중에 연료가 다닳은 경우 -1을 리턴한다.
return dist;
}
public static boolean done() { //모든 승객을 다 데려다줬는지 확인
for(int i=0; i<m; i++) {
if(carr[i]!=null) {return false;}
}
return true;
}
public static int simulate() {
boolean doneright = true; // 탐색 결과 승객을 태울 수 있거나 바래다 줄수 있다면 true 아니면 false
while(!done()) { // 모든승객을 바래다 줄때 까지 while문 실행
int min = Integer.MAX_VALUE; // 가장 가까운 승객의 거리
Ctmr custo =null; //가장 가까운 승객의 정보 저장
PriorityQueue<Info> pq = new PriorityQueue<>(); //가장 짧고 행좌표가 가장작고 열좌표가 가장 작은 고객을 찾기 위한 heap
bfs(new Pair(cx,cy), pq); //고객을 찾기 위해 bfs 를 돌림
if(pq.isEmpty()) { //주어진 연료로 갈수 태울수 있는 고객이 없을때 pq는 안에 아무것도 없다.
doneright = false;
break;
}
Info dest = pq.poll(); //탐색결과 태울 수 있는 승객들을 담고 그중 가장 가깝고 조건에 잘맞는 승객을 pq 의 가장 앞에서 찾는다.
min = dest.dist;
custo = carr[dest.num-1];
cx = dest.x; //택시의 위치를 고객의 취치로 갱신
cy = dest.y;//택시의 위치를 고객의 취치로 갱신
rk-=min; //고객에게 가는 거리만큼 빼준다.
int doneres = bfs2(new Pair(cx,cy),new Pair(custo.ex,custo.ey)); //고객의 현재위치에서 목적지까지 가는데 필요한 거리
if(doneres==-1) { //가는 길에 연료가 다 닳을 경우 -1 return 됨 이때 while문 빠져나와야한다.
doneright = false; break;
}
rk-=doneres; //쓴 연료만 큼 빼주고
rk += (doneres*2); //쓴연료의 두배만큼 더해준다.
cx=custo.ex;
cy= custo.ey;
carr[dest.num-1]=null; //데려다준 고객은 null로한다.
map[custo.sx][custo.sy]=0; //데려다준 고객은 map 에서 지워버린다.
}
if(doneright==false) {return -1;} //탐색 결과 태울 승객이 없거나 태워도 바래다 줄수 없다면 -1리턴
return rk;
}
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());
k = Integer.parseInt(st.nextToken());
rk=k;
map= new int[n][n];
carr = new Ctmr[m];
for(int i=0; i<n; i++) {
st = new StringTokenizer(br.readLine());
for(int j=0; j<n; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
if(map[i][j]==1) {
map[i][j]=-1;
}
}
}
st = new StringTokenizer(br.readLine());
cx = Integer.parseInt(st.nextToken())-1;
cy = Integer.parseInt(st.nextToken())-1;
for(int i=0; i<m;i++) {
st = new StringTokenizer(br.readLine());
carr[i]= new Ctmr(Integer.parseInt(st.nextToken())-1,Integer.parseInt(st.nextToken())-1,Integer.parseInt(st.nextToken())-1,Integer.parseInt(st.nextToken())-1);
int x = carr[i].sx;
int y = carr[i].sy;
map[x][y]=i+1;
}
System.out.println(simulate());
}
}
- 어려웠던점1: 일단 모든 승객을 한번의 bfs로 탐색 후 priority queue 에 넣어서 가장 가까운 승객을 찾아준다.=> 시간초과 해결 방법
- 어려웠던점2: bfs 에선 출발지점과 목적지점이 같을 경우 pq 에 넣어줘야함, bfs2 에선 출발지점과 목적지점이 같을 경우 바로 0을 반환
'백준 > 삼성기출' 카테고리의 다른 글
| 마법사상어와파이어스톰 - 20058번(Java) (0) | 2021.09.23 |
|---|---|
| 마법사상어와토네이도-20057번(Java) (0) | 2021.09.22 |
| 어른상어 - 19237번 (JAVA) (0) | 2021.09.16 |
| 마법사 상어와 파이어볼 / 시뮬레이션 (0) | 2021.04.23 |
| 큐빙 (0) | 2021.04.19 |
