문제
링크 : https://www.acmicpc.net/problem/19238
해결과정
삼성 기출 중에서 역대급으로 날 괴롭혔던 문제였다. (아직 스무개 좀 넘게 풀었지만..)
골드2 문제인데도 역시나 구현 문제는 티어 대비 소요시간이 너무 긴 것 같다.
(하루에 하나만 풀어도 진이 빠진다)
문제점을 찾기위해서 디버깅을 정말 많이 했다.
정렬조건과 더불어 좌표를 판별하여 현재 상태를 정의하는 과정이 너무 중요했던 문제였다.
고려해야할 요소가 많았고 이에 따라 단계별로 처리해야하는 것들이 너무 많았다.
해결과정은 다음과 같다.
방문해야하는 곳은 승객(시작점)과 도착점들이었다.
먼저 어떤 자료형을 쓰는게 좋을까 고민하다가, 이차원배열로 처리하기로 했다.
static Point[][] destArr;
static boolean[][] destVisit;destArr는 목적지를 담은 배열로 승객(시작점) – 도착점을이 한 쌍인 열로 이루어져 있다.(2열)
여기에는 Point라는 static class를 사용하여 좌표를 담았다.
destVisit 는 이를 방문했는지 여부를 판단하기 위한 boolean 배열로 위와 동일한 구조이다.
전반적인 로직은 Taxi 객체를 우선순위 큐에 담아 BFS 방식으로 돌아간다.
Taxi 클래스는 다음과 같다.
static class Taxi implements Comparable<Taxi> {
int y, x, fuel, used, status;
public Taxi(int y, int x, int fuel, int used, int status) {
this.y = y;
this.x = x;
this.fuel = fuel;
this.used = used;
this.status = status;
}
@Override
public int compareTo(Taxi o) {
if (this.fuel == o.fuel) {
if (this.y == o.y) {
return this.x - o.x;
}
return this.y - o.y;
}
return o.fuel - this.fuel;
}
}택시에는 좌표값과 더불어 연료량, 연료 소모량, 현재 상태를 변수로 넣었다.
status(현재상태)는 승객을 태웠는지 여부를 판단하는 것으로
승객이 없다면 BASIC_STATUS (-1) 라는 상수를 할당해주었고
승객이 탔다면 승객에 해당하는 행 번호(destArr 의 행 인덱스)를 지정해 주었다.
이를 기반으로 초기좌표부터 BFS를 수행했다.
고려했던 순서는 다음과 같다.
1. 가장 가까운 승객한테 간다. (거리가 같다면 행이 작은, 행이같다면 열이 작은 승객이 우선순위를 갖는다)
이를 큐에서 정렬하기위해 우선순위 큐를 사용했고 Taxi 클래스에 정렬 조건을 오버라이드 했다.
추가로, 이동 단계별로 순차적으로 탐색을하기위해서 연료량도 정렬 조건에 추가했다.
즉, 1. 연료량이 많은 순 (= 출발점으로부터 가까운 순) -> 2. 행 순 -> 3. 열 순 으로 정렬을 했다.
2. 승객을 태운다.
승객을 태웠다면 destVisit에 방문체크를 해준다.
여기서부터는 연료 사용량을 누적하기 시작한다.
승객을 태움과 동시에 visit배열을 초기화(resetVisit() 메서드)한다.
초기화는 입력으로 받았던 isWall 이라는 벽 정보(boolean 이차원 배열)를 깊은복사로 가져오는 것이다.
마지막으로 큐를 비워준다. (우선순위에 따라 가장 가까운 승객한테 도착한 상황이므로)
3. 승객을 태웠다면 그 승객의 도착점으로 이동한다.
승객을 태우고나서 부터는 연료 사용량을 추가적으로 누적해주어야 했다.
이는 한칸 이동할때마다 연료량은 -1, 사용량은 +1 을 해주면 됐다.
중요한건, 사용량은 항상 승객을 태울때만 기록을 해야한다는 점이었다.
승객이 없을땐 사용량을 다뤄줄 필요가 없었다.
그래서 평소(승객이 안탄 빈 택시)에는 사용량을 0으로 고정했고 승객이 탔을때부터 누적을 해주었다.
4. 도착점에 승객을 내려준다.
도착점을 destVisit에 방문체크를 해준다.
승객을 내려주었으므로 visit 배열을 초기화한다.
큐를 비워준다.
승객을 내려주었으므로 승객을태우고 누적했던 연료사용량의 두배를 연료량에 더해준다.
추가로 연료 사용량을 0으로 초기화한다.
마지막으로 destVisit을 모두 체크하여 (isAllCleared() 메서드) 승객을 모두 이동시켰는지 판단한다.
모두 이동시켰다면 남은 연료량을 answer에 넣어주고 리턴한다.
모두 이동시키지 않았다면 1번으로 돌아가 다음 승객을 찾는다.
참고로 status를 정의하는 과정(출발점,도착점 검증)을 두 번 반복시켰는데
이는 도착점과 다른 출발점(승객위치)이 일치할 수 있어서 귀찮아서 무식하게 두 번 반복시켰다.
이 과정때문에 불필요한 경우에도 두 번씩 검증을해서 시간이 꽤 오래 걸린상태로 통과가 된 것 같다.
다만, 실제로는 더 여러 명의 승객이나 도착점이 한 좌표위에 있을 수 있고, 없을 수 도 있으므로
검증을 하는 메서드를 만들어서 확인을 해야할 것 같은데
채점용 테케에는 두 좌표만 겹치는 경우만 있는지 통과가 된 것 같다.
이 과정은 보완할 필요가 있어보인다.
추가로 문제 해결에 도움을 주었던 반례모음이다.
https://www.acmicpc.net/board/view/58112
제출
코드
import java.io.*;
import java.util.*;
public class Main {
static int N, M;
static boolean[][] isWall;
static boolean[][] visit;
static Point[][] destArr;
static boolean[][] destVisit;
static int[] dy = {0, -1, 0, 1}, dx = {-1, 0, 1, 0};
static final int BASIC_STATUS = -1;
static int answer = -1;
static class Point {
int y, x;
public Point(int y, int x) {
this.y = y;
this.x = x;
}
@Override
public boolean equals(Object o) {
Point p = (Point)o;
if (this.y == p.y && this.x == p.x) {
return true;
}
return false;
}
}
static class Taxi implements Comparable<Taxi> {
int y, x, fuel, used, status;
public Taxi(int y, int x, int fuel, int used, int status) {
this.y = y;
this.x = x;
this.fuel = fuel;
this.used = used;
this.status = status;
}
@Override
public int compareTo(Taxi o) {
if (this.fuel == o.fuel) {
if (this.y == o.y) {
return this.x - o.x;
}
return this.y - o.y;
}
return o.fuel - this.fuel;
}
}
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());
int fuel = Integer.parseInt(st.nextToken());
isWall = new boolean[N][N];
visit = new boolean[N][N];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
int num = Integer.parseInt(st.nextToken());
if (num == 1) {
isWall[i][j] = true;
visit[i][j] = true;
}
}
}
st = new StringTokenizer(br.readLine());
int taxiY = Integer.parseInt(st.nextToken()) - 1;
int taxiX = Integer.parseInt(st.nextToken()) - 1;
destArr = new Point[M][2];
destVisit = new boolean[M][2];
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
destArr[i][0] = new Point(Integer.parseInt(st.nextToken()) - 1, Integer.parseInt(st.nextToken()) - 1);
destArr[i][1] = new Point(Integer.parseInt(st.nextToken()) - 1, Integer.parseInt(st.nextToken()) - 1);
}
Taxi taxi = new Taxi(taxiY, taxiX, fuel, 0, BASIC_STATUS);
findPath(taxi);
System.out.println(answer);
}
static void findPath(Taxi taxi) {
PriorityQueue<Taxi> pq = new PriorityQueue<>();
pq.add(taxi);
visit[taxi.y][taxi.x] = true;
while (!pq.isEmpty()) {
Taxi now = pq.poll();
Point nowPoint = new Point(now.y, now.x);
int nowFuel = now.fuel;
int nowUsed = now.used;
int nowStatus = now.status;
if (nowFuel < 0) {
continue;
}
//status 정의
for (int i = 0; i < 2; i++) {
int[] checkIdx = isOnDest(nowPoint, nowStatus);
if (checkIdx != null) {//목적지 위일 경우<
int rowIdx = checkIdx[0];
int colIdx = checkIdx[1];
if (nowStatus == BASIC_STATUS && colIdx == 0) {//시작점 도착 (승객이 안탄 상태)
if (!destVisit[rowIdx][colIdx]) {
destVisit[rowIdx][colIdx] = true;
nowStatus = rowIdx;
resetVisit();
pq.clear();
}
} else if (nowStatus == rowIdx && colIdx == 1) {//도착점 도착 (승객이 탄상태 + 승객의 도착점)
if (!destVisit[rowIdx][colIdx]) {
destVisit[rowIdx][colIdx] = true;
nowStatus = BASIC_STATUS;
resetVisit();
pq.clear();
nowFuel += (nowUsed * 2);
nowUsed = 0;
if (isAllCleared()) {
answer = Math.max(answer, nowFuel);
return;
}
}
}
}
}
for (int i = 0; i < 4; i++) {
int nextY = now.y + dy[i];
int nextX = now.x + dx[i];
if (0 <= nextY && nextY < N && 0 <= nextX && nextX < N && !visit[nextY][nextX]) {
visit[nextY][nextX] = true;
if (nowStatus != BASIC_STATUS) {
pq.add(new Taxi(nextY, nextX, nowFuel - 1, nowUsed + 1, nowStatus));
} else {
pq.add(new Taxi(nextY, nextX, nowFuel - 1, nowUsed, nowStatus));
}
}
}
}
}
static int[] isOnDest(Point point, int status) {
for (int i = 0; i < M; i++) {
for (int j = 0; j < 2; j++) {
if (status == BASIC_STATUS) {
if (j == 0 && !destVisit[i][j] && point.equals(destArr[i][j])) {
return new int[] {i, j};
}
} else {
if (j == 1 && i == status && !destVisit[i][j] && point.equals(destArr[i][j])) {
return new int[] {i, j};
}
}
}
}
return null;
}
static void resetVisit() {
for (int i = 0; i < N; i++) {
visit[i] = Arrays.copyOf(isWall[i], N);
}
}
static boolean isAllCleared() {
for (boolean[] pair : destVisit) {
for (boolean dest : pair) {
if (!dest) {
return false;
}
}
}
return true;
}
}