문제 링크 ▶︎ 백준 스타트 택시 19238
문제 파악
문제를 보자마자 어떻게 풀지 막막했는데 먼저 해야할 것은 택시가 어떤 승객을 태우러 가는지에 대한 로직이 필요하다고 생각했다.
그리고 승객을 태우고 나서 목적지에 가는 로직도 필요하다. 즉, 최단거리를 탐색하는 과정이 승객을 태우러 갈때 한번, 승객을 태우고 목적지로 갈 때 한번, 총 2번의 최단 거리 탐색이 필요하다고 생각했다.
여러명의 승객이 택시에서 동일한 거리의 위치에 존재한다면 제일 위, 제일 왼쪽의 순서로 태워야한다는 조건으로 인해서 dir의 순서로 처리할 수 있을 거라 생각했는데 반례가 존재해서 따로 승객의 우선 순위를 찾는 로직도 필요하다.
걍 어렵다.
접근 방법
- Main
- i 번째 승객의 시작좌표를 start[i] 에, 목적지 좌표를 end[i] 에 저장하고, done이라는 HashSet을 통해서 택시를 탄 승객을 셋에 저장해서 중복되지 않도록 처리한다.
- 모든 승객이 타기 전까지 while문을 도는데 현재 택시에서 가장 가까운 승객의 위치와 거리를 next() 함수로 찾은 다음 해당 승객까지 가는 거리를 연료에서 빼준다.
- 만약 연료를 다 써버리면 -1을 출력하고 그게 아니라면 승객을 태워서 목적지까지 이동을 한다.
- 목적지에 애초에 이동할 수 없거나 아니면 연료가 없어서 이동할 수 없다면 -1을 출력하고 아니라면 택시의 위치를 목적지의 위치로 바꾸고 이동한 거리의 두배만큼 연료를 추가하고 해당 승객은 done 셋에 추가해서 탑승완료임을 기억한다.
- while문을 다 수행했다는 것은 승객을 모두 태웠다는 것이므로 남은 연료를 출력한다.
- distance (승객을 태운 택시가 목적지까지 얼마의 거리로 가는지 리턴)
- 동서남북 dir 을 만들고 불린 배열 visit을 만들고, 시작좌표는 방문처리를 해두고 q를 만든 후, 시작 좌표와 거리0 을 int[] 로 넣는다.
- while문을 순회하면서 q에서 빼낸 좌표가 도착좌표라면 그까지의 거리를 리턴하고, 그게 아니라면 동서남북을 돌면서 이동하고 방문하지 않은 곳이라면 방문한다.
- 방문한 곳은 방문 처리를 하고 거리는 방금 거리의 +1 을 해주고 좌표와 거리를 q에 넣는다.
- 만약 while문을 모두 다 돌아도 도착좌표를 못찾았다면 -1을 리턴한다.
- next (택시가 승객을 찾으러가서 몇번째 idx의 승객을 태우러 가며, 거리가 얼마나 걸리는 지 리턴)
- 동서남북 dir 을 만들고 불린 배열 visit을 만들고, 택시좌표는 방문처리를 해두고 q를 만든 후, 택시 좌표와 거리0 을 int[] 로 넣는다.
- 또 List box가 필요한데 이것은 택시에서 최단 거리에 있는 승객들의 좌표를 저장하는 곳이다.
이후 이 리스트를 행,열 순서로 정렬해서 태워야하는 손님 한명을 뽑을 것이다. - 택시에서 최단 거리인 승객을 태워야 하기 때문에 최단거리를 기억하기 위해 min_dist를 만들고 초기화는 맥스값으로 해뒀다.
- while 문을 순회하면서 뺀 값의 2번째 인덱스값, 즉 택시에서의 거리가 현재 min_dist 인 현재 택시-승객의 최단거리 보다 큰 좌표는 볼 필요가 없기 때문에 그냥 브레이크 걸어버렸다. 이 조건문을 걸지않으면 쓸데없는 좌표를 계속 탐색하게 되므로 시간초과에 걸리게 된다. while문을 시작하자마자는 택시-승객의 최단거리를 찾지 못하지만 나중에 찾게되면 쓸데없는 좌표를 안가서 시간을 줄일 수 있다.
- 만약 승객들이 서있는 좌표를 모아둔 start배열을 순회하며 현재 q에서 뺀 좌표가 승객의 위치와 같다면 box에 좌표를 저장하고, min_dist를 승객-택시 거리로 저장해둔다. 그 전의 if문을 통과했기 때문에 현재는 이 승객이 최단거리 위치에 있는 것이다.
- 동서남북을 돌면서 조건을 만족하고 방문하지 않은 곳은 방문하고 q에 추가한다.
- 만약 box에 아무것도 없다면, 택시가 방문할 수 있는 승객이 없는 것이라 -1을 리턴하고, box배열을 0번째 인덱스(행)가 작은 순으로 정렬한다. 만약 행이 같다면 열이 작은 순으로 정렬한다. 이후 첫번째 좌표를 리턴한다.
코드 구현
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
import java.io.IOException;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken()); // 승객 수
int fuel = Integer.parseInt(st.nextToken()); // 연료
int[][] road = new int[n][n];
for (int i = 0; i < n; i++) {
String[] tokens = br.readLine().split(" ");
for (int j = 0; j < n; j++) {
road[i][j] = Integer.parseInt(tokens[j]);
}
}
int[][] start = new int[m][2];
int[][] end = new int[m][2];
st = new StringTokenizer(br.readLine());
int taxi_y = Integer.parseInt(st.nextToken())-1;
int taxi_x = Integer.parseInt(st.nextToken())-1;
for (int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
start[i][0] = Integer.parseInt(st.nextToken())-1;
start[i][1] = Integer.parseInt(st.nextToken())-1;
end[i][0] = Integer.parseInt(st.nextToken())-1;
end[i][1] = Integer.parseInt(st.nextToken())-1;
}
HashSet<Integer> done = new HashSet<>();
while(done.size() < m){
int[] out = next(taxi_y, taxi_x, start, road, done);
if(out[0] == -1){
fuel = -1;
break;
}
int idex = out[0];
int consumed = out[1];
fuel -= consumed;
if(fuel < 0){
fuel = -1;
break;
}
int dist = distance(start[idex][0],start[idex][1],end[idex][0],end[idex][1],road);
if(dist == -1 || fuel < dist){
fuel = -1;
break;
}
done.add(idex);
taxi_y = end[idex][0];
taxi_x = end[idex][1];
fuel += dist;
}
System.out.println(fuel);
}
public static int distance(int before_y, int before_x, int after_y, int after_x, int[][] road) {
int n = road.length;
int[][] dir = {{-1,0},{0,-1},{1,0},{0,1}};
boolean[][] visit = new boolean[n][n];
Queue<int[]> q = new ArrayDeque<>();
q.add(new int[]{before_y, before_x,0});
visit[before_y][before_x] = true;
while (!q.isEmpty()) {
int[] curr = q.remove();
if (curr[0] == after_y && curr[1] == after_x) {
return curr[2];
}
for (int[] d : dir) {
int ny = curr[0] + d[0];
int nx = curr[1] + d[1];
if (ny >= 0 && ny < n && nx >= 0 && nx < n && road[ny][nx] == 0 && !visit[ny][nx]) {
visit[ny][nx] = true;
q.add(new int[]{ny, nx, curr[2]+1});
}
}
}
return -1;
}
public static int[] next(int y, int x, int[][] start, int[][] road, HashSet<Integer> done) {
int n = road.length;
int[][] dir = {{-1,0},{0,-1},{1,0},{0,1}};
boolean[][] visit = new boolean[n][n];
Queue<int[]> q = new ArrayDeque<>();
q.add(new int[]{y, x, 0});
visit[y][x] = true;
List<int[]> box = new ArrayList<>();
int min_dist = Integer.MAX_VALUE;
while (!q.isEmpty()) {
int[] curr = q.remove();
if(curr[2] > min_dist) {
break;
}
for(int i = 0; i < start.length; i++){
if(!done.contains(i) && curr[0] == start[i][0] && curr[1] == start[i][1]){
box.add(new int[]{i, curr[2]});
min_dist = curr[2];
}
}
for (int[] d : dir) {
int ny = curr[0] + d[0];
int nx = curr[1] + d[1];
if(ny >= 0 && ny < n && nx >= 0 && nx < n && road[ny][nx] == 0 && !visit[ny][nx]) {
visit[ny][nx] = true;
q.add(new int[]{ny, nx, curr[2]+1});
}
}
}
if(box.size() == 0){
return new int[]{-1, -1};
}
box.sort((a, b) -> {
if(start[a[0]][0] != start[b[0]][0]){ // start[idx][0] -> row
return start[a[0]][0] - start[b[0]][0];
}
return start[a[0]][1] - start[b[0]][1];
});
return box.get(0);
}
}
개선 사항
2시간 정도를 푼 것 같은데 조건이 굉장히 많아서 까다로웠다. 이 코드를 누군가 보고 이해할 수 있을까.. 너무 더러운 코드를 짠 것 같지만 여튼 풀어서 만족한다.
처음부터 조건을 정리하면서 풀었다면 풀이 시간을 줄일 수 있었을 것 같다. 상좌를 순서로 승객을 태우는 조건이나 최단거리에 해당하는 승객을 발견했으면 그 거리를 비교하는데 쓰는 것도 충분히 미리 생각할 수 있었는데 시간초과에 걸리자 시간을 줄이기 위해서 생각해보니 떠올랐다.
조건이 복잡한 문제일수록 손코딩에 시간을 투자하고 정리를 좀 하고 풀어야겠다.
junyoun9dev@gmail.com