[백준] 19238. 스타트 택시(java)

문제 링크

📝 문제

스타트링크가 "스타트 택시"라는 이름의 택시 사업을 시작했다. 스타트 택시는 특이하게도 손님을 도착지로 데려다줄 때마다 연료가 충전되고, 연료가 바닥나면 그 날의 업무가 끝난다.

택시 기사 최백준은 오늘 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)