백준 19238 스타트 택시 - 삼성 SW 역량 테스트 기출

백준 19238 스타트 택시 - 삼성 SW 역량 테스트 기출

1. 문제 링크

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

19238번: 스타트 택시

 

2. 문제 해결에 대한 아이디어

1. 승객 클래스를 구현했으며, 들어온 순서대로 번호를 매겼다.

   . 승객 번호를 board에 마킹할 수 있다.

   . 승객 번호로 ArrayList<Customer> customerInfo(승객 정보)에 접근할 수 있다.

2. 택시의 이동은 아래와 같이 진행 된다.

   . 가장 짧은 거리에 있는 승객을 태우며, 여러 명일 경우 좌표의 행이 제일 작고 열이 제일 작은 승객을 태운다.

   . 승객을 태운 뒤에, 목적지까지 이동하며 "탑승 -> 목적지"까지 사용한 연료의 2배 만큼 연료를 채운다.

   . 중간에 연료가 떨어질 경우, 영업 종료 한다.

3. 태울 승객의 위치를 선별하기 위해, Pair 클래스에 compareTo를 구현했다.

4. compareTo를 통해 sorting하여 첫번째 값에 위치한 승객을 태운다.

5. 승객을 태우고 나서 승객의 위치는 0으로 바꿔준다.

6. 연료의 계산은 이동이 끝난 뒤 진행하며, 연료를 오버해서 사용한 경우 종료한다.

   . 출발 -> 탑승 : 연료가 0이 되면 종료

   . 탑승 -> 목적 : 연료가 0이 되어도 충전할 것이기 때문에 종료하지 않음

7. 사용한 연료는 visit에 기록했으며, 이동이 끝난 뒤에 택시 연료와 비교했다.

8. 다다를 수 없는 목적지가 있음을 생각해야했다. (아래 표 참고)

벽	목적지
벽	벽

9. 따라서, 목적지까지의 BFS가 완료된 후 목적지 위치에 비용이 기록되었는지 확인이 필요했다.

3. 코드

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;

public class Main {
	static class Customer {
		int no;
		int sy, sx, ey, ex;

		public Customer(int no, int sy, int sx, int ey, int ex) {
			super();
			this.no = no;
			this.sy = sy;
			this.sx = sx;
			this.ey = ey;
			this.ex = ex;
		}
	}

	static class Taxi {
		int y, x, oil;
		int customerNo;

		public Taxi(int y, int x, int oil) {
			super();
			this.y = y;
			this.x = x;
			this.oil = oil;
		}

	}

	static class Pair implements Comparable<Pair> {
		int y, x;

		public Pair(int y, int x) {
			super();
			this.y = y;
			this.x = x;
		}

		@Override
		public int compareTo(Pair o) {
			if (this.y == o.y)
				return this.x - o.x;
			return this.y - o.y;
		}
	}

	static int N, M, L;
	static int[] dirY = { 0, 0, 1, -1 };
	static int[] dirX = { 1, -1, 0, 0 };
	static int[][] visit;
	static int[][] board;
	static Taxi t;
	static ArrayList<Customer> customerInfo = new ArrayList<>();
	static int driveCnt = 0;
	static int answer = 0;

	public static void main(String[] args) throws IOException {
		BufferedReader br;
//		br = new BufferedReader(new FileReader(
//				"C:\\Users\\admin\\git\\java-algorithm\\src\\main\\java\\boj\\삼성기출\\스타트택시_19238\\input.txt"));
		br = new BufferedReader(new InputStreamReader(System.in));

		// 승객 위치보정 필요
		String[] nml = br.readLine().split(" ");
		N = Integer.parseInt(nml[0]);
		M = Integer.parseInt(nml[1]);
		L = Integer.parseInt(nml[2]);

		board = new int[N][N];

		for (int i = 0; i < N; i++) {
			String[] line = br.readLine().split(" ");
			for (int j = 0; j < N; j++) {
				board[i][j] = Integer.parseInt(line[j]);
				if (board[i][j] == 1)
					board[i][j] = -1;
			}
		}
		String[] taxi = br.readLine().split(" ");
		int y = Integer.parseInt(taxi[0]) - 1;
		int x = Integer.parseInt(taxi[1]) - 1;
		t = new Taxi(y, x, L);

		for (int i = 0; i < M; i++) {
			String[] line = br.readLine().split(" ");
			int sy = Integer.parseInt(line[0]) - 1;
			int sx = Integer.parseInt(line[1]) - 1;
			int ey = Integer.parseInt(line[2]) - 1;
			int ex = Integer.parseInt(line[3]) - 1;
			customerInfo.add(new Customer(i + 1, sy, sx, ey, ex)); // 접근할때 번호 - 1
			board[sy][sx] = i + 1;
		}

		while (true) {
			if (driveCnt == M) {
				answer = t.oil;
				break;
			}

			if (!pickCustomer()) {
				answer = -1;
				break;
			}

			if (!drive()) {
				answer = -1;
				break;
			}
		}

		if (driveCnt != M) {
			answer = -1;
		}

		System.out.println(answer);
	}

	// 승객 태우고 이동
	static boolean drive() {
		visit = new int[N][N];
		Customer c = customerInfo.get(t.customerNo - 1);
		int ey = c.ey;
		int ex = c.ex;

		Pair p = new Pair(t.y, t.x);
		Queue<Pair> q = new LinkedList<>();
		q.add(p);
		visit[t.y][t.x] = 1; // 비용 보정 필요
		while (!q.isEmpty()) {
			Pair now = q.poll();
			int y = now.y;
			int x = now.x;

			if (y == ey && x == ex) {
				break;
			}

			for (int d = 0; d < 4; d++) {
				int yy = y + dirY[d];
				int xx = x + dirX[d];

				if (yy < 0 || xx < 0 || yy >= N || xx >= N || board[yy][xx] == -1 || visit[yy][xx] != 0)
					continue;

				visit[yy][xx] = visit[y][x] + 1;
				q.add(new Pair(yy, xx));
			}
		}
		if (visit[ey][ex] == 0)
			return false;
		int spendOil = visit[ey][ex] - 1;
		if (t.oil >= spendOil) {
			t.y = ey;
			t.x = ex;
			t.oil += spendOil;
			++driveCnt;
			return true;
		} else {
			return false;
		}

	}

	// 승객 찾기
	static boolean pickCustomer() {
		int minDis = -1;
		visit = new int[N][N];
		ArrayList<Pair> candi = new ArrayList<>();
		Queue<Pair> q = new LinkedList<>();
		q.add(new Pair(t.y, t.x));
		if (board[t.y][t.x] > 0) {
			t.customerNo = board[t.y][t.x];
			board[t.y][t.x] = 0;
			return true;
		}
		visit[t.y][t.x] = 1; // 나중에 -1 해야함
		while (!q.isEmpty()) {
			Pair now = q.poll();
			int y = now.y;
			int x = now.x;

			if (board[y][x] > 0) {
				if (minDis == -1) {
					minDis = visit[y][x];
					candi.add(new Pair(y, x));
				} else {
					if (minDis == visit[y][x]) {
						candi.add(new Pair(y, x));
					} else {
						break;
					}
				}
			}

			for (int d = 0; d < 4; d++) {
				int yy = y + dirY[d];
				int xx = x + dirX[d];

				if (yy < 0 || xx < 0 || yy >= N || xx >= N || board[yy][xx] == -1 || visit[yy][xx] != 0)
					continue;

				visit[yy][xx] = visit[y][x] + 1;
				q.add(new Pair(yy, xx));
			}
		}
		if (candi.isEmpty()) {
			return false;
		}

		// 후보 리스트 완성 후 태울 손님 찾기
		Collections.sort(candi);
		int y = candi.get(0).y;
		int x = candi.get(0).x;
		// 손님 태우러갈때 쓴 연료
		int spendOil = visit[y][x] - 1;
		if (t.oil >= spendOil) {
			t.y = y;
			t.x = x;
			t.oil -= spendOil;
			t.customerNo = board[y][x];
			board[y][x] = 0;
			return true;
		} else {
			return false;
		}

	}
}

 

4. 채점 결과

 

5. 느낀 점

1. 도달할 수 없는 목적지를 생각해내는게 쉽지 않았다. 이거 하나 때문에 한 시간을 고민했다.

2. 삼성의 이런 디테일.. 디테일에 악마가 있다...