[BOJ 19238] 스타트 택시 (Java)

https://www.acmicpc.net/problem/19238

19238번: 스타트 택시

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

public class Main_BOJ_19238 {
	static class Node implements Comparable<Node>{
		int r, c, dist;
		public Node(int r, int c, int dist) {
			this.r = r;
			this.c = c;
			this.dist = dist;
		}
		public int compareTo(Node o) {
			if (this.dist==o.dist) {
				if (this.r==o.r) {
					return this.c-o.c;
				}
				return this.r-o.r;
			}
			return this.dist-o.dist;
		}
	}
	static int[] dr= {-1,1,0,0};
	static int[] dc= {0,0,-1,1};
	static int N, M;
	static long fuel;
	static int[][] map;
	static int[][] passengers;
	static boolean[][] check;
	static int start_r, start_c;
	static boolean flag=false;
	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());
		fuel=Long.parseLong(st.nextToken());
		map=new int[N+1][N+1];
		passengers=new int[M+1][5];
		for (int i=1; i<=N; i++) {
			st=new StringTokenizer(br.readLine());
			for (int j=1; j<=N; j++) {
				map[i][j]=Integer.parseInt(st.nextToken());
			}
		}
		st=new StringTokenizer(br.readLine());
		start_r=Integer.parseInt(st.nextToken());
		start_c=Integer.parseInt(st.nextToken());
		for (int i=1; i<=M; i++) {
			st=new StringTokenizer(br.readLine());
			passengers[i][0]=Integer.parseInt(st.nextToken());
			passengers[i][1]=Integer.parseInt(st.nextToken());
			passengers[i][2]=Integer.parseInt(st.nextToken());
			passengers[i][3]=Integer.parseInt(st.nextToken());
			passengers[i][4]=0; //완료 여부 표시
		}
		int cnt=0;
		while (cnt<M) {
			int[] p=findShortestPath();
			if (fuel<p[3] || p[0]==0) {
				flag=true;
				break;
			}
			fuel-=p[3];
			//그 고객의 목적지까지 이동한다
			int sum=move(p[1],p[2]);
			//시작점 바꿔주고, 연료 갱신, 완료 여부 표시 등등..
			if (fuel<sum || sum==-1) {
				flag=true;
				break;
			}
			start_r=p[1];
			start_c=p[2];
			fuel=((fuel-sum)+(2*sum));
			passengers[p[0]][4]=1;
			cnt++;
		}
		if (!flag)
			System.out.println(fuel);
		else
			System.out.println(-1);
		
	}
	private static int move(int dest_r, int dest_c) {
		check=new boolean[N+1][N+1];
		Queue<Node> q=new LinkedList<>();
		q.add(new Node(start_r, start_c, 0));
		check[start_r][start_c]=true;
		while (!q.isEmpty()) {
			Node now=q.poll();
			if (now.r==dest_r && now.c==dest_c) {
				return now.dist;
			}
			for (int i=0; i<4; i++) {
				int nr=now.r+dr[i];
				int nc=now.c+dc[i];
				if (nr<=0 || nc<=0 || nr>N || nc>N) continue;
				if (map[nr][nc]==0 && !check[nr][nc]) {
					check[nr][nc]=true;
					q.add(new Node(nr, nc, now.dist+1));
				}
			}
		}
		return -1;
	}
	
	
	private static int[] findShortestPath() {
		int[] ans=new int[4];
		ArrayList<Node> li=new ArrayList<>();
		check=new boolean[N+1][N+1];
		Queue<Node> q=new LinkedList<>();
		q.add(new Node(start_r, start_c, 0));
		check[start_r][start_c]=true;
		while (!q.isEmpty()) {
			Node now=q.poll();
			if (isPassenger(now.r, now.c)>0) {
				li.add(new Node(now.r, now.c, now.dist));
			}
			for (int i=0; i<4; i++) {
				int nr=now.r+dr[i];
				int nc=now.c+dc[i];
				if (nr<=0 || nc<=0 || nr>N || nc>N) continue;
				if (map[nr][nc]==0 && !check[nr][nc]) {
					check[nr][nc]=true;
					q.add(new Node(nr, nc, now.dist+1));
				}
			}
		}
		if (li.size()==0) return ans;
		Collections.sort(li);
		int num=isPassenger(li.get(0).r, li.get(0).c);
		ans[0]=num;
		ans[1]=passengers[num][2];
		ans[2]=passengers[num][3];
		ans[3]=li.get(0).dist;
		start_r=li.get(0).r;
		start_c=li.get(0).c;
		return ans;
	}
	private static int isPassenger(int nr, int nc) {
		for (int i=1; i<=M; i++) {
			if (nr==passengers[i][0] && nc==passengers[i][1] && passengers[i][4]==0) {
				return i;
			}
		}
		return 0;
	}

}

구현+시뮬레이션+BFS 문제이다.

 

1) 가장 짧은 최단 경로를 갖는 고객을 찾기(bfs)

2) 그 고객의 위치로 간 후 그 고객의 목적지까지 가기(bfs)

 

연료를 체크하여 목적지까지 갈 때 부족하면 return -1, 갈 수 없는 경우면 return -1을 해준다.

 

isPassenger() 함수로 각 위치를 방문할 때마다 고객이 있는지 체크해줬는데,

사실 이럴 필요 없이 map에 그 위치를 고객 번호로 표시하면 O(1) 만에 체크가 가능하다..

그리고 findShortestPath() 함수에서 배열로 리턴할 필요 없이 고객의 번호만 리턴하면,

passengers 배열로 출발지, 도착지 위치를 찾을 수 있다. 

또한 findShortestPath() 함수에서 즉석해서 fuels 를 빼주는 형태를 취하면 더 간단해진다.

 

다음 풀이는 위 아이디어를 참고하여 푼 풀이.

포인트: 현재 택시의 위치가 고객의 위치, 고객의 도착지일 수 있는거 생각하기

map에다 고객이 있는 위치는 고객의 번호로 표시해줘서 탐색할때 고객인지 자동으로 O(1) 만에 체크되게 하기

BFS 탐색할 때 꼭 같은 node 객체 할 필요 없다!

 

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

public class Main_BOJ_19238 {
	static class Node implements Comparable<Node>{
		int num, r, c, dist;
		public Node(int num, int r, int c, int dist) {
			this.num=num;
			this.r = r;
			this.c = c;
			this.dist = dist;
		}
		public int compareTo(Node o) {
			if (this.dist==o.dist) {
				if (this.r==o.r) {
					return this.c-o.c;
				}
				return this.r-o.r;
			}
			return this.dist-o.dist;
		}
	}
	static int[] dr= {-1,1,0,0};
	static int[] dc= {0,0,-1,1};
	static int N, M;
	static long fuel;
	static int[][] map;
	static int[][] passengers;
	static boolean[][] check;
	static int start_r, start_c;
	static boolean flag=false;
	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());
		fuel=Long.parseLong(st.nextToken());
		map=new int[N+1][N+1];
		passengers=new int[M+1][4];
		for (int i=1; i<=N; i++) {
			st=new StringTokenizer(br.readLine());
			for (int j=1; j<=N; j++) {
				map[i][j]=Integer.parseInt(st.nextToken());
				if (map[i][j]==1) map[i][j]=-1;
			}
		}
		st=new StringTokenizer(br.readLine());
		start_r=Integer.parseInt(st.nextToken());
		start_c=Integer.parseInt(st.nextToken());
		for (int i=1; i<=M; i++) {
			st=new StringTokenizer(br.readLine());
			passengers[i][0]=Integer.parseInt(st.nextToken());
			passengers[i][1]=Integer.parseInt(st.nextToken());
			passengers[i][2]=Integer.parseInt(st.nextToken());
			passengers[i][3]=Integer.parseInt(st.nextToken());
			map[passengers[i][0]][passengers[i][1]]=i;
		}
		int cnt=0;
		while (cnt<M) {
			int num=findShortestPath();
			if (num==-1) {
				flag=true;
				break;
			}
			//그 고객의 목적지까지 이동한다
			int sum=move(passengers[num][2], passengers[num][3]);
			//시작점 바꿔주고, 연료 갱신, 완료 여부 표시 등등..
			if (fuel<sum || sum==-1) {
				flag=true;
				break;
			}
			fuel=((fuel-sum)+(2*sum));
			map[passengers[num][0]][passengers[num][1]]=0;	//방문 표시
			start_r=passengers[num][2];
			start_c=passengers[num][3];
			cnt++;
		}
		if (!flag)
			System.out.println(fuel);
		else
			System.out.println(-1);
		
	}
	private static int move(int dest_r, int dest_c) {
		check=new boolean[N+1][N+1];
		Queue<int[]> q=new LinkedList<>();
		q.add(new int[] {start_r, start_c, 0});
		check[start_r][start_c]=true;
		while (!q.isEmpty()) {
			int[] now=q.poll(); 
			if (now[0]==dest_r && now[1]==dest_c) {
				return now[2];
			}
			for (int i=0; i<4; i++) {
				int nr=now[0]+dr[i];
				int nc=now[1]+dc[i];
				if (nr<=0 || nc<=0 || nr>N || nc>N) continue;
				if (map[nr][nc]!=-1 && !check[nr][nc]) {
					check[nr][nc]=true;
					q.add(new int[] {nr, nc, now[2]+1});
				}
			}
		}
		return -1;
	}
	
	
	private static int findShortestPath() {
		ArrayList<Node> li=new ArrayList<>();
		check=new boolean[N+1][N+1];
		Queue<int[]> q=new LinkedList<>();
		q.add(new int[] {start_r, start_c, 0});
		check[start_r][start_c]=true;
		while (!q.isEmpty()) {
			int[] now=q.poll();
			if (map[now[0]][now[1]]!=0) {	//고객일 경우
				li.add(new Node(map[now[0]][now[1]], now[0], now[1], now[2]));
			}
			for (int i=0; i<4; i++) {
				int nr=now[0]+dr[i];
				int nc=now[1]+dc[i];
				if (nr<=0 || nc<=0 || nr>N || nc>N) continue;
				if (map[nr][nc]!=-1 && !check[nr][nc]) {
					check[nr][nc]=true;
					q.add(new int[] {nr, nc, now[2]+1});
				}
			}
		}
		if (li.size()==0) return -1;
		Collections.sort(li);
		int cost=li.get(0).dist;
		if (fuel<cost) return -1;
		start_r=li.get(0).r;
		start_c=li.get(0).c;
		fuel-=cost;
		return li.get(0).num;
	}

}