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

문제 링크 - https://www.acmicpc.net/problem/19238

🌱 문제

(자세한건 링크 보기)

🌱 풀이

먼저 손님의 정보 (손님의 위치, 손님이 도착하려는곳이 위치, 택시로부터 손님까지의 거리)를 담을수 있는 Info 객체를 하나 생성하였다.
그리고 ArrayList<Info> 형태의 personList에 각 손님의 정보를 담았다.
정렬조건 (거리 오름차순, 행 오름차순, 열 오름차순)을 설정하여 personList를 정렬하고 0번째인덱스의 손님이 타겟손님이 되어, 해당 손님을 처리하는 과정을 M(손님 수)번 반복하도록 구현하였다.

주의할점

if(target.dist==-1) { // 우선순위 1번손님이 갈 수 없는 위치에 있다면 -1출력하고 종료 
	System.out.println(-1);
	return;
}

처음에 이 부분을 고려 안해서 틀렸었다.
정렬조건을 통해 걸러진 타겟손님이 벽으로 인해 갈수 없는 위치인 경우가 있을 수 있으므로, 이 조건을 넣어줘야 한다.

if(oil<0) { //여기서 oil<=0 으로해서 틀렸음 연료가 0 미만일때부터 연료 바닥난걸로 취급하는 듯 
System.out.println(-1);
return;
}

문제에 이동하는 도중에 연료가 바닥나면 이동에 실패하고, 그 날의 업무가 끝난다. 승객을 목적지로 이동시킨 동시에 연료가 바닥나는 경우는 실패한 것으로 간주하지 않는다. 이렇게 쓰여있는데 난 연료가 0이 되는순간 바닥나는 건 줄 알고 if(oil<=0)으로 했다가 틀렸다. 0 미만일 때 부터 바닥난걸로 취급하는거 주의 해야겠다.

느낀점

이런 비슷한 구현 문제 나올때마다 나는 필요한 멤버변수들 쭉 생각해서, 클래스 만들고, 거기(이문제에서는 Info 클래스)에 모든거 담아놓는 방식으로 푼다.
리스트에 매번 접근해야해서 손님이 많은경우에 매우 오래걸릴것 같긴한데 이렇게 한 클래스에 다 모아두는(?) 방식밖에 생각이 안나서 그냥 이렇게 풀어야겠따 ...

🌱 코드

package week05.boj_19238;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Queue;
import java.util.StringTokenizer;

//19238. 스타트 택시 
public class Somyeong {
	
	static class Info implements Comparable<Info> {
		int pr, pc; //person_r, person_c
		int ar,ac;//arrive_r, arrive_c
		int dist;
		public Info(int pr, int pc,int ar, int ac) {
			this.pr=pr;
			this.pc=pc;
			this.ar=ar;
			this.ac=ac;
			this.dist=0; // 처음 생성시 거리는 0으로 초기화 
		}
		
		//거리순으로 오름차순정렬, 행 오름차순 정렬, 열 오름차순 정렬 
		@Override
		public int compareTo(Info i) {
			if(this.dist==i.dist) {
				if(this.pr==i.pr) {
					return this.pc-i.pc;
				}
				return this.pr-i.pr;
			}
			return this.dist-i.dist;
		}
		
	}
	static class Point{
		int r, c;
		public Point(int r,int c) {
			this.r=r;
			this.c=c;
		}
	}
	static int N,M,oil;
	static int tr,tc;//택시의 좌표 
	static int arr[][];
	static ArrayList<Info> personList;
	static int dr[]= {-1,1,0,0};
	static int dc[]= {0,0,-1,1};
	static int dist[][];
	
	
	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());
		oil=Integer.parseInt(st.nextToken());
	
		
		arr=new int[N][N];
		dist=new int[N][N];
		personList=new ArrayList<Info>();
		
		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());
		tr=Integer.parseInt(st.nextToken());
		tc=Integer.parseInt(st.nextToken());
		tr--; tc--; //인덱스 0부터라서 
		for(int i=0; i<M; i++) {
			st=new StringTokenizer(br.readLine());
			int person_r=Integer.parseInt(st.nextToken());
			int person_c=Integer.parseInt(st.nextToken());
			int arrive_r=Integer.parseInt(st.nextToken());
			int arrive_c=Integer.parseInt(st.nextToken());
			//M개의 손님정보 personList에 담기 
			personList.add(new Info(person_r-1,person_c-1,arrive_r-1,arrive_c-1));//인덱스 0부터라서 
		}
		
		for(int i=0; i<M; i++) { //사람수 만큼 반복
			initDist(); // dist[][] 배열 -1로 초기화 
			bfs(tr,tc); //택시의 위치 (r,c)를 기준으로 각 손님의 거리까지의 최단경로 구하기
			
			//제일 가까운 손님 구하기
			for(int k=0; k<personList.size(); k++) {
				Info cur = personList.get(k);
				cur.dist=dist[cur.pr][cur.pc];
			} 
			Collections.sort(personList); //거리 오름차순, 행 오름차순, 열 오름차순 정렬 
			
			Info target = personList.get(0); //우선순위 가장높은 손님 
			if(target.dist==-1) { // 우선순위 1번손님이 갈 수 없는 위치에 있다면 -1출력하고 종료 
				System.out.println(-1);
				return;
			}
			
			oil=oil-target.dist;
			
			initDist();
			bfs(target.pr,target.pc); // 타겟손님위치 기준으로 bfs 실행 ( 타겟손님 도착위치 까지의 거리 구하기 위해)
			oil-=dist[target.ar][target.ac]; // 도착하는데 걸린 만큼 빼주기 
			
			//택시위치 -> 타겟손님 위치 -> 타겟손님 도착위치 순서로 갔고, 이때  연료가 0미만이 될 경우 -1출력하고 끝내기 
			if(oil<0) { //여기서 oil<=0 으로해서 틀렸음 연료가 0 미만일때부터 연료 바닥난걸로 취급하는 듯 
				System.out.println(-1);
				return;
			}
			oil+=dist[target.ar][target.ac]*2;
			personList.remove(0); // 타겟손님 제거 
			tr=target.ar; //택시좌표를 타겟손님의 도착좌표로 갱신 
			tc=target.ac;
			
		}
		System.out.println(oil);
	}
	public static void bfs(int r, int c) { //(r,c)기준으로 dist[][] 구하는 bfs
		dist[r][c]=0;
		Queue<Point> q= new ArrayDeque<Point>();
		q.offer(new Point(r,c));
		while(!q.isEmpty()) {
			Point cur = q.poll();
			for(int d=0; d<4; d++) {
				int nr=cur.r+dr[d];
				int nc=cur.c+dc[d];
				if(nr>=0 && nc>=0 && nr<N && nc<N&& arr[nr][nc]==0&&dist[nr][nc]==-1) {
					dist[nr][nc]=dist[cur.r][cur.c]+1;
					q.offer(new Point(nr,nc));
				}
			}
		}
	}
	
	public static void initDist() { //dist[][] 배열 -1로 초기화 
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				dist[i][j]=-1;
			}
		}
	}
}