https://www.acmicpc.net/problem/19238
19238번: 스타트 택시
첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다
www.acmicpc.net
[문제]
스타트링크가 "스타트 택시"라는 이름의 택시 사업을 시작했다. 스타트 택시는 특이하게도 손님을 도착지로 데려다줄 때마다 연료가 충전되고, 연료가 바닥나면 그 날의 업무가 끝난다.
택시 기사 최백준은 오늘 M명의 승객을 태우는 것이 목표이다. 백준이 활동할 영역은 N×N 크기의 격자로 나타낼 수 있고, 각 칸은 비어 있거나 벽이 놓여 있다. 택시가 빈칸에 있을 때, 상하좌우로 인접한 빈칸 중 하나로 이동할 수 있다. 알고리즘 경력이 많은 백준은 특정 위치로 이동할 때 항상 최단경로로만 이동한다.
M명의 승객은 빈칸 중 하나에 서 있으며, 다른 빈칸 중 하나로 이동하려고 한다. 여러 승객이 같이 탑승하는 경우는 없다. 따라서 백준은 한 승객을 태워 목적지로 이동시키는 일을 M번 반복해야 한다. 각 승객은 스스로 움직이지 않으며, 출발지에서만 택시에 탈 수 있고, 목적지에서만 택시에서 내릴 수 있다.
백준이 태울 승객을 고를 때는 현재 위치에서 최단거리가 가장 짧은 승객을 고른다. 그런 승객이 여러 명이면 그중 행 번호가 가장 작은 승객을, 그런 승객도 여러 명이면 그중 열 번호가 가장 작은 승객을 고른다. 택시와 승객이 같은 위치에 서 있으면 그 승객까지의 최단거리는 0이다. 연료는 한 칸 이동할 때마다 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개의 줄에 걸쳐 각 승객의 출발지의 행과 열 번호, 그리고 목적지의 행과 열 번호가 주어진다. 모든 출발지와 목적지는 빈칸이고, 모든 출발지는 서로 다르며, 각 손님의 출발지와 목적지는 다르다.
[코드]
import java.util.*;
class Taxi implements Comparable<Taxi>{
int x,y,move;
public Taxi(int x, int y, int move) {
this.x=x;
this.y=y;
this.move=move;
}
@Override
public int compareTo(Taxi o) {
// TODO Auto-generated method stub
if(this.move==o.move) { // 이동거리
if(this.x==o.x) // 행
return this.y-o.y;
else // 열
return this.x-o.x;
}
return this.move-o.move;
}
}
class Passenger {
int num,sx,sy,ex,ey;
public Passenger(int num, int sx, int sy, int ex, int ey) {
this.num=num;
this.sx=sx;
this.sy=sy;
this.ex=ex;
this.ey=ey;
}
}
public class BaekJoon_19238 {
static int n,m,fuel;
static int[][] map;
static Taxi taxi;
static int[] dx= {-1,0,1,0};
static int[] dy= {0,-1,0,1};
static Passenger[] passenger;
static Queue<Integer>[][] passengermap;
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
m=sc.nextInt();
fuel=sc.nextInt();
map=new int[n+1][n+1];
passenger=new Passenger[m+1];
passengermap=new LinkedList[n+1][n+1];
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
passengermap[i][j]=new LinkedList<>();
map[i][j]=sc.nextInt();
// 벽이 있는 곳은 -1로 변경(승객 넘버링을 1부터 하기 위함)ㄴ
if(map[i][j]==1)
map[i][j]=-1;
}
}
// 처음 택시의 시작 지점
int x=sc.nextInt();
int y=sc.nextInt();
taxi=new Taxi(x,y,0);
for(int i=1;i<=m;i++) {
int sx=sc.nextInt();
int sy=sc.nextInt();
int ex=sc.nextInt();
int ey=sc.nextInt();
passenger[i]=new Passenger(i,sx,sy,ex,ey); // 승객 정보 저장
passengermap[sx][sy].add(i); // 승객들 맵에 승객의 번호 저장
}
for(int i=0;i<m;i++) {
if(!find_Passenger()) { // 태울 승객이 없는 경우
System.out.println(-1);
return;
}
/*
* find_Passenger 결과로 taxi에는 탑승한 승객의 출발 위치가
* taxi.move에는 해당 승객을 태우기까지 택시가 이동한 칸수가 저장되어 있다.
*/
int Time=taxi.move;
int index=passengermap[taxi.x][taxi.y].poll();
// 목적지에 도달할 수 없다면 -1 출력
if(!go_Destination(passenger[index].ex,passenger[index].ey)) {
System.out.println(-1);
return;
}
/*
* find_Passenger() -> go_Destination() 결과로 taxi.move에는
* 승객을 태우기까지 택시가 이동한 칸수 + 승객이 목적지에 도착할때 까지 택시가 이동한 횟수가 저장되어 있다.
* 전체 연료에서 해당 값 빼주기
*/
fuel-=taxi.move;
// 모든 승객을 처리하기 전 연료가 떨어지면 -1 출력
if(fuel<0) {
System.out.println(-1);
return;
}
else { // 연료가 남아있는 상태에서 목적지에 도착했다면 연료 채우기
fuel+=(2*(taxi.move-Time));
taxi.move=0;
}
}
System.out.println(fuel);
return;
}
// 현재 택시 위치에서 조건에 알맞는 승객 태우기
static boolean find_Passenger() {
Queue<Taxi> q=new LinkedList<>();
ArrayList<Taxi> candidate=new ArrayList<>(); // 택시에 태울 승객 후보가 저장될 연결리스트
boolean[][] visited=new boolean[n+1][n+1];
q.offer(taxi);
visited[taxi.x][taxi.y]=true;
while(!q.isEmpty()) {
Taxi now=q.poll();
// 택시에 탑승할 승객 후보가 있고, 먼저 태운 승객보다 현재 승객의 이동 횟수가 크다면 넘어간다.
if(!candidate.isEmpty()&&candidate.get(0).move<now.move)
continue;
// 이동횟수가 더 적고 now 위치에 승객이 있다면 후보군에 삽입
if(!passengermap[now.x][now.y].isEmpty()) {
candidate.add(now);
continue;
}
for(int i=0;i<4;i++) {
int nx=now.x+dx[i];
int ny=now.y+dy[i];
// 맵을 벗어났거나, 이미 방문한 칸이거나, 벽인 경우 넘어간다.
if(nx<1||ny<1||nx>n||ny>n||visited[nx][ny]||map[nx][ny]==-1)
continue;
visited[nx][ny]=true;
q.offer(new Taxi(nx,ny,now.move+1)); // 이동거리 +1
}
}
// 연결리스트가 빈 경우는 태울 수 있는 승객이 없는 경우
if(candidate.isEmpty())
return false;
Collections.sort(candidate);
taxi=candidate.get(0); // 연결리스트의 맨 앞에있는 승객 택시에 탑승
return true;
}
// 태운 승객 목적지까지 최단거리로 이동
static boolean go_Destination(int ex, int ey) {
Queue<Taxi> q=new LinkedList<>();
q.offer(taxi);
boolean[][] visited=new boolean[n+1][n+1];
visited[taxi.x][taxi.y]=true;
while(!q.isEmpty()) {
Taxi now=q.poll();
// 목적지에 도착했다면
if(now.x==ex&&now.y==ey) {
taxi=now; // 택시의 위치를 갱신해주고 true 반환
return true;
}
for(int i=0;i<4;i++) {
int nx=now.x+dx[i];
int ny=now.y+dy[i];
// 맵을 벗어났거나, 이미 방문한 칸이거나, 벽인 경우 넘어간다.
if(nx<1||ny<1||nx>n||ny>n||visited[nx][ny]||map[nx][ny]==-1)
continue;
visited[nx][ny]=true;
q.offer(new Taxi(nx,ny,now.move+1)); // 이동거리 +1
}
}
return false;
}
}
[고찰]
이번 문제는 여태까지 백준 문제를 풀어보면서 가장 코드가 긴 문제였던 것 같다. 난이도는 골드 4밖에 안됐지만 문제와 코드가 길다보니 체감 난이도가 더 높게 느껴졌던 것 같다. 혼자 처음부터 끝까지 구현하는데 어려움을 느껴 다른 사람의 코드를 참고하면서 차근차근 구현해나갔다.
우선 이 문제의 가장 큰 핵심은 택시가 탑승할 승객을 찾을 때(find_Passenger 함수)도 최단거리로 이동하고, 승객을 태운 뒤 목적지에 갈때(go_Destination 함수)도 최단거리로 이동해야 한다는 점이다. 즉, 두 번의 BFS 알고리즘을 사용해야 한다는 말과 같다. 막상 이 두 함수를 구현하는 것은 어렵지 않았다.
더 어려웠던 점은 저장해야할 자료구조를 정하는 것이었다. 이렇게 구현해야 할 조건이 많은 시뮬레이션 문제는 효율적이고 접근하기 쉬운 자료구조를 선택하여 알맞은 정보를 저장하는 것이 중요한데 아직 이 부분이 많이 부족한 것 같다.
'백준' 카테고리의 다른 글
| [백준_2075번] N번째 큰 수 (0) | 2022.02.08 |
|---|---|
| [백준_1202번] 보석 도둑 (0) | 2022.01.19 |
| [백준_1939번] 중량제한 (0) | 2022.01.14 |
| [백준_9342번] 염색체 (0) | 2022.01.11 |
| [백준_1253번] 좋다 (0) | 2022.01.11 |