🚕백준 : 스타트 택시

🔑문제

19238번: 스타트 택시
Lv : 골드 2

🔑문제 풀이 흐름

1. 택시 위치, 손님 위치 저장하기

1) 택시 위치
택시 시작 위치를 배열로 저장한다.

static int[] taxi;
// 택시 시작 위치
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
taxi = new int[] { x - 1, y - 1 };

2) 손님 위치

• Customer 객체를 만들어 출발지와 목적지를 저장
• customers 리스트에 객체를 저장

//객체 생성
class Customer {
	int[] depart; //출발지점 
	int[] dest; //도착지점
	int path; //거리 저장
	boolean arrived; //완료한 손님인지

	public Customer(int[] depart, int[] dest, int path, boolean arrived) {
		super();
		this.depart = depart;
		this.dest = dest;
		this.path = path;
		this.arrived = arrived;
	}
}

		// 손님의 위치 배열
		customers = new ArrayList<>(M);

		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int x1 = Integer.parseInt(st.nextToken());
			int y1 = Integer.parseInt(st.nextToken());
			int x2 = Integer.parseInt(st.nextToken());
			int y2 = Integer.parseInt(st.nextToken());

			Customer cus = new Customer(new int[] { x1 - 1, y1 - 1 }, new int[] { x2 - 1, y2 -1 }, 0, false);
			customers.add(cus);

		}

2. 손님의 수만큼 반복하여 이동

한 사이클에서 수행하는 과정:

• 이번에 태울 손님 선택 (choose)
• 택시 위치에서 승객 위치까지 이동 (pickUp)
• 승객 목적지까지 이동 (dropDown)

end 변수: 연료 부족이나 도달 불가 시 반복 종료 및 -1 출력 처리

		for (int i = 0; i < M; i++) {
			end = false; // 초기화
			// 1) 이번에 픽업할 손님을 고르는 메서드
			int custIdx = choose();
			if (end) {
				break;
			}
//			 2) 손님 픽업하기
			pickUp(custIdx);
			if (end) {
				break;
			}
//			// 손님을 목적지까지 이동하기.
			dropDown(custIdx);
			if (end) {
				break;
			}
		}

3. choose : 가장 가까운 승객 선택

• 거리 기준으로 가장 가까운 승객 선택
• 거리 같으면 행 번호, 같으면 열 번호 순으로 결정
• BFS로 각 승객까지 최단 거리 계산

	private static int choose() {
    //가장 가까운 손님을 픽업해야 한다. 
		minPath = Integer.MAX_VALUE;
		minIdx = -1;
		// 객체를 돌기
		for (int i = 0; i < M; i++) {
			Customer cus = customers.get(i);

			if (cus.arrived) { // 이미 처리한 손님이면 pass
				continue;
			}
			int p = distance(taxi[0], taxi[1], cus.depart[0], cus.depart[1]); // 거리를 구하기
			if (p == -1) continue; 
			if (p < minPath) {
				minPath = p;
				minRow = cus.depart[0];
				minCol = cus.depart[1];
				minIdx = i;
			} else if (p == minPath) {
			    if (cus.depart[0] < minRow || (cus.depart[0] == minRow && cus.depart[1] < minCol)) {
			        minRow = cus.depart[0];
			        minCol = cus.depart[1];
			        minIdx = i;
			    }
			}
		}
		//모든 손님 접근 불가
		if( minIdx == -1) {
			end = true;
			return -1;
		}
		// 손님을 태운 거 처리하기
		customers.get(minIdx).arrived = true;

		return minIdx;
	}

4. pickUp : 손님 픽업

• 택시 -> 승객 출발지 이동
• 연료 소모 반영, 택시 위치 업데이트
• 도달 불가 또는 연료 부족 시 end = true 처리

	private static void pickUp(int custIdx) {

		int targetPath = 0;
		int targetX = 0;
		int targetY = 0;

		// 택시 위치에서 손님 depart까지의 거리
		targetX = customers.get(custIdx).depart[0];
		targetY = customers.get(custIdx).depart[1];

		targetPath = distance(taxi[0], taxi[1], targetX, targetY);

		//distance가 -1로 나오는 경우도 end가 되도록 처리해주기
		if (targetPath == -1 || oil - targetPath < 0) {
		    end = true;
		    return;
		}
		oil -= targetPath;
		taxi[0] = targetX;
		taxi[1] = targetY;
	}

5. dropDown : 목적지까지 이동

• 승객 출발지 -> 목적지 이동
• 이동 거리만큼 연료 소모, 도착 시 연료 2배 충전
• 연료 부족 시 end = true 처리

	private static void dropDown(int custIdx) {

		int departX = customers.get(custIdx).depart[0];
		int departY = customers.get(custIdx).depart[1];

		int destX = customers.get(custIdx).dest[0];
		int destY = customers.get(custIdx).dest[1];

		int dist = distance(taxi[0], taxi[1], destX, destY);
		if (dist == -1 || oil - dist < 0) { // 도달 불가 또는 연료 부족
		    end = true;
		    return;
		}
		oil = oil - dist + dist * 2;
		taxi[0] = destX;
		taxi[1] = destY;

	}

6. distance : 최단 거리 계산

dfs를 이용하여 최단 거리 계산

	private static int distance(int startX, int startY, int targetX, int targetY) {
	    boolean[][] visited = new boolean[N][N];
	    Queue<int[]> q = new LinkedList<>();
	    q.offer(new int[]{startX, startY, 0}); // {x, y, depth}
	    visited[startX][startY] = true;

	    while (!q.isEmpty()) {
	        int[] cur = q.poll();
	        int x = cur[0];
	        int y = cur[1];
	        int d = cur[2];

	        // 목적지 도착
	        if (x == targetX && y == targetY) {
	            return d;
	        }
	        for (int k = 0; k < 4; k++) {
	            int nx = x + di[k];
	            int ny = y + dj[k];

	            if (nx >= 0 && nx < N && ny >= 0 && ny < N && map[nx][ny] == 0 && !visited[nx][ny]) {
	                visited[nx][ny] = true;
	                q.offer(new int[]{nx, ny, d + 1});
	            }
	        }
	    }
	    // 도달 불가
	    return -1;
	}

🔑회고

이 문제에서 가장 까다로웠던 점은 도달 불가의 경우를 처리하는 것이었다.
생성한 거의 모든 메서드에서 도달이 불가한 경우를 고려해야 했고, 놓치는 부분도 많았다.

이런 조건을 꼼꼼하게 검토하여 코드를 작성해야겠다...