📝 문제
스타트링크가 "스타트 택시"라는 이름의 택시 사업을 시작했다. 스타트 택시는 특이하게도 손님을 도착지로 데려다줄 때마다 연료가 충전되고, 연료가 바닥나면 그 날의 업무가 끝난다.
택시 기사 최백준은 오늘 M명의 승객을 태우는 것이 목표이다. 백준이 활동할 영역은 N×N 크기의 격자로 나타낼 수 있고, 각 칸은 비어 있거나 벽이 놓여 있다. 택시가 빈칸에 있을 때, 상하좌우로 인접한 빈칸 중 하나로 이동할 수 있다. 알고리즘 경력이 많은 백준은 특정 위치로 이동할 때 항상 최단경로로만 이동한다.
M명의 승객은 빈칸 중 하나에 서 있으며, 다른 빈칸 중 하나로 이동하려고 한다. 여러 승객이 같이 탑승하는 경우는 없다. 따라서 백준은 한 승객을 태워 목적지로 이동시키는 일을 M번 반복해야 한다. 각 승객은 스스로 움직이지 않으며, 출발지에서만 택시에 탈 수 있고, 목적지에서만 택시에서 내릴 수 있다.
백준이 태울 승객을 고를 때는 현재 위치에서 최단거리가 가장 짧은 승객을 고른다. 그런 승객이 여러 명이면 그중 행 번호가 가장 작은 승객을, 그런 승객도 여러 명이면 그중 열 번호가 가장 작은 승객을 고른다. 택시와 승객이 같은 위치에 서 있으면 그 승객까지의 최단거리는 0이다. 연료는 한 칸 이동할 때마다 1만큼 소모된다. 한 승객을 목적지로 성공적으로 이동시키면, 그 승객을 태워 이동하면서 소모한 연료 양의 두 배가 충전된다. 이동하는 도중에 연료가 바닥나면 이동에 실패하고, 그 날의 업무가 끝난다. 승객을 목적지로 이동시킨 동시에 연료가 바닥나는 경우는 실패한 것으로 간주하지 않는다.
모든 승객을 성공적으로 데려다줄 수 있는지 알아내고, 데려다줄 수 있을 경우 최종적으로 남는 연료의 양을 출력하는 프로그램을 작성하시오.
입력
첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다.
다음 줄부터 N개의 줄에 걸쳐 백준이 활동할 영역의 지도가 주어진다. 0은 빈칸, 1은 벽을 나타낸다.
다음 줄에는 백준이 운전을 시작하는 칸의 행 번호와 열 번호가 주어진다. 행과 열 번호는 1 이상 N 이하의 자연수이고, 운전을 시작하는 칸은 빈칸이다.
그다음 줄부터 M개의 줄에 걸쳐 각 승객의 출발지의 행과 열 번호, 그리고 목적지의 행과 열 번호가 주어진다. 모든 출발지와 목적지는 빈칸이고, 모든 출발지는 서로 다르며, 각 손님의 출발지와 목적지는 다르다.
출력
모든 손님을 이동시키고 연료를 충전했을 때 남은 연료의 양을 출력한다. 단, 이동 도중에 연료가 바닥나서 다음 출발지나 목적지로 이동할 수 없으면 -1을 출력한다. 모든 손님을 이동시킬 수 없는 경우에도 -1을 출력한다.
💡 Solution
❗ 조심할 점
- 최단 거리가 같은 손님이 두명이면 손님의 x좌표로 비교해 작은거!! 그것도 같으면 y좌표 비교
- 손님을 태울수 없는 경우, 연료가 없을 경우 -1 출력 단, 목적지에 왔을때 연료가 0인건 괜찮
- 손님카운트를 뺄때 리스트에서도 손님을 제거해줘야함
- 손님위치와 도착지점을 class로 만듬
- 손님수만큼 택시 이동하기(메소드 만들기)
- 택시에서 최단거리인 손님 찾기(bfs 사용) -> 손님 찾았는데 연료가 없음 -1 출력, 택시 위치 변경
- 손님 태우고 목적지까지 최단 거리 찾기(bfs 사용) -> 목적지 도착했는데 연료가 음수면 -1 출력, 아니면 연료 2배
🔑 code
package Baekjoon;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
class Guest{
int nowx;
int nowy;
int arrivex;
int arrivey;
public Guest(int nowx, int nowy, int arrivex, int arrivey) {
super();
this.nowx = nowx;
this.nowy = nowy;
this.arrivex = arrivex;
this.arrivey = arrivey;
}
}
public class 스타트택시_19238 {
static int n,m,fuel;
static int[][] road;
static int taxix,taxiy;
static ArrayList<Guest> guest;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
fuel = sc.nextInt();
road = new int[n][n];
for(int i=0; i<n;i++) {
for(int j=0;j<n;j++) {
road[i][j]= sc.nextInt();
}
}
taxix = sc.nextInt()-1; //taxi x 위치
taxiy = sc.nextInt()-1; //taxi x 위치
//guest 위치와 목표 지점 저장 배열
guest = new ArrayList<>();
//guest 위치와 목표 지점 배열에 추가하기
for(int i=0; i<m;i++) {
int startx = sc.nextInt()-1;
int starty = sc.nextInt()-1;
int endx = sc.nextInt()-1;
int endy = sc.nextInt()-1;
guest.add(new Guest(startx,starty,endx,endy));
}
//손님 수 만큼 택시 이동
int firstguestnum = m; //나중엔 guest 수가 바뀜
for(int i=0; i<firstguestnum;i++) {
findGuest();
}
System.out.println(fuel);
}
private static void findGuest() {
int shortest = Integer.MAX_VALUE; //최단거리
int shorttestguestidx = -1; //최단거리일떄 인덱스
for(int i=0; i<m;i++) {
int nowx = guest.get(i).nowx; //게스트 x위치
int nowy = guest.get(i).nowy; //게스트 y위치
int starttoguest = bfs(nowx,nowy); //택시 ~ i 손님까지 최단 거리
if(starttoguest == -1) { //손님을 이동할 수 없는 경우
System.out.println(-1);
System.exit(0);
}
if(shortest >=starttoguest){ //현재 손님의 최단 거리가 가장 짧을떄
if(shortest == starttoguest) { //만약 같으면
if(guest.get(shorttestguestidx).nowx <guest.get(i).nowx) {//기존에 있던 최단거리의 행이 더 작으면 continue
continue;
}else if (guest.get(shorttestguestidx).nowx == guest.get(i).nowx) {//두개 같으면 열까지 비교
if(guest.get(shorttestguestidx).nowy < guest.get(i).nowy) {
continue;
}
}
}
shortest = starttoguest; //최단 거리 갱신
shorttestguestidx = i; //인덱스 갱신
}
}
int tempx = guest.get(shorttestguestidx).nowx; //최단 거리 손님의 x
int tempy = guest.get(shorttestguestidx).nowy; //최단 거리 손님의 y
int arrivex = guest.get(shorttestguestidx).arrivex; //최단 거리 손님 도착 지점 x
int arrivey = guest.get(shorttestguestidx).arrivey; //최단 거리 손님 도착 지점 y
//택시 위치 변경
taxix = tempx;
taxiy = tempy;
fuel -= shortest; //연료 뺴기
if(fuel<0) { //사람은 남아있는데 연료가 없으면
System.out.println(-1);
System.exit(0);
}
//guest태우고 목적지로 가기
int guesttoarrive = bfs(arrivex,arrivey);
taxix = arrivex;
taxiy = arrivey;
fuel-=guesttoarrive; //최단 거리 뺴기
if(fuel<0) {
System.out.println(-1);
System.exit(0);
}
m-=1; //손님 한명 빼기
guest.remove(shorttestguestidx);//값도 지우기
fuel+= guesttoarrive*2; //연료 2배
}
private static int bfs(int nowx, int nowy) {
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[] {taxix,taxiy,0});
int[] dx = {1,-1,0,0};
int[] dy = {0,0,1,-1};
boolean[][] check = new boolean[n][n];
check[taxix][taxiy] = true;
while(!queue.isEmpty()) {
int[] nowPosition = queue.poll();
int nx = nowPosition[0];
int ny = nowPosition[1];
int cnt = nowPosition[2];
if(nx==nowx &&ny== nowy) return cnt;
for(int i=0; i<4;i++) {
int nextx = nx+dx[i];
int nexty = ny+dy[i];
if(nextx>=0 && nextx<n && nexty>=0 && nexty<n && !check[nextx][nexty] && road[nextx][nexty]!= 1) {
check[nextx][nexty] = true;
queue.add(new int[] {nextx,nexty,cnt+1});
}
}
}
return -1;
}
}
📚알고리즘 분류
너비 우선 탐색(bfs), 그래프 이론(graphs), 그래프 탐색(graph_traversal), 구현(implementation), 시뮬레이션(simulation)
