[백준]JAVA - 19238번: 스타트 택시

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

19238번: 스타트 택시

풀이

이번 문제는 조건이 많아서 고민할 게 많았다.

구동 순서는 아래와 같다.

 

1. 택시 위치로부터 가장 가까운 손님을 찾는다. (findPerson) - bfs
2. 가까운 손님의 목적지까지 이동 (goTaxi) - bfs
3. 위 내용을 반복한다.

1. 택시 위치로부터 가장 가까운 손님을 찾는다.

public static void findPerson(int x, int y, int dis) {
    boolean[][] visited = new boolean[N][N];
    PriorityQueue<Move> q = new PriorityQueue<>();
    q.add(new Move(x, y, dis));
    visited[x][y] = true;
        
    while (!q.isEmpty()) {
        Move now = q.poll();
            
        for (int i=0; i<arrPerson.size(); i++) {
            if (now.x == arrPerson.get(i).x-1 && now.y == arrPerson.get(i).y-1) {
                nearPerson.add(new Move(now.x, now.y, now.dis));
            }
        }
            
        for (int i=0; i<4; i++) {
            int nx = now.x + dx[i];
            int ny = now.y + dy[i];
                
            if (nx < 0 || ny < 0 || nx > N-1 || ny > N-1 || map[nx][ny] == 1 || visited[nx][ny]) continue;
                
            q.add(new Move(nx, ny, now.dis+1));
            visited[nx][ny] = true;
        }
    }
}

bfs를 이용해서 손님들의 위치를 우선순위 큐에 넣어준다. 우선순위 큐를 이용해서 가까운 손님이 여러 명이면 그중 행 번호가 가장 작은 승객을, 그런 승객도 여러 명이면 그중 열 번호가 가장 작은 승객 조건을 해결해준다.

 

2. 가까운 손님의 목적지까지 이동 (goTaxi) - bfs

public static int goTaxi(int x, int y, int targetX, int targetY) {
    boolean[][] visited = new boolean[N][N];
    Queue<Move> q = new LinkedList<>();
    q.add(new Move(x, y, 0));
        
    while (!q.isEmpty()) {
        Move now = q.poll();
            
        if (now.x == targetX && now.y == targetY) {
            return now.dis;
        }
            
        for (int i=0; i<4; i++) {
            int nx = now.x + dx[i];
            int ny = now.y + dy[i];
                
            if (nx < 0 || ny < 0 || nx > N-1 || ny > N-1 || map[nx][ny] == 1 || visited[nx][ny]) continue;
                
            q.add(new Move(nx, ny, now.dis+1));
            visited[nx][ny] = true;
        }
    }
        
    return -1;
}

손님을 태우고 목적지까지 이동하는 bfs 이다. 기본적인 bfs 이기 때문에 어렵지 않게 이해할 수 있을 것이라고 생각한다.

 

3. 위 내용을 반복한다.

반복하는 과정에서 더 이상 태울 승객이 없거나 가장 가까운 손님이 없을 경우, 연료가 다 떨어졌을 경우를 예외처리해주면  해결할 수 있다. 

 

필자는 배열의 크기를 -1로 만들어서 택시의 위치와 손님들의 위치, 목적지가 -1로 생성됐는데 여러 가지 함수를 돌리니까 굉장히 헷갈렸다. 꼼꼼하게 살펴보면서 어려움 없이 해결했지만 배열의 크기를 늘려서 문제를 해결하는 걸 추천한다.

 

 

<최종코드>

import java.io.*;
import java.util.*;
 
public class Main {
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, 1, 0, -1};
    static int[][] map;
    static ArrayList<Move> nearPerson;
    static ArrayList<Person> arrPerson;
    static int N, M;
    
    public static class Person {
        int x;
        int y;
        int targetX;
        int targetY;
        
        public Person(int x, int y, int targetX, int targetY) {
            this.x = x;
            this.y = y;
            this.targetX = targetX;
            this.targetY = targetY;
        }
    }
    
    public static class Move implements Comparable<Move>{
        int x;
        int y;
        int dis;
        
        public Move (int x, int y, int dis) {
            this.x = x;
            this.y = y;
            this.dis = dis;
        }
        
        public int compareTo (Move o) {
            if (this.dis == o.dis){
                if (this.x == o.x){
                    return this.y - o.y; 
                } else {
                    return this.x - o.x;
                }
            } else {
                return this.dis - o.dis;
            }
        }
    }
    
    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 K = Integer.parseInt(st.nextToken()); // 초기 연료
        
        map = new int[N][N];
        
        for (int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j=0; j<N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        st = new StringTokenizer(br.readLine());
        int tX = Integer.parseInt(st.nextToken());
        int tY = Integer.parseInt(st.nextToken());
        
        arrPerson = new ArrayList<>();  // 손님 위치와 목적지
        nearPerson = new ArrayList<>(); // 택시에서 제일 가까운 손님 
        
        for (int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int targetX = Integer.parseInt(st.nextToken());
            int targetY = Integer.parseInt(st.nextToken());
            
            arrPerson.add(new Person(x, y, targetX, targetY));
        }
        
        while (true) {
            // 더 이상 손님이 없을 경우
            if (arrPerson.isEmpty()) {
                System.out.println(K);
                return;
            }
            
            nearPerson.clear();
            findPerson(tX-1, tY-1, 0);
            
            // 가까운 손님이 없을 경우
            if (nearPerson.isEmpty()) {
                System.out.println(-1);
                return;
            }
            
            int dist = 0;
            Move now = nearPerson.get(0); // 제일 가까운 손님
            
            K -= now.dis; // 택시에서 손님까지의 거리
            
            for (int i=0; i<arrPerson.size(); i++) {
                if (now.x == arrPerson.get(i).x-1 && now.y == arrPerson.get(i).y-1) {
                    dist = goTaxi(arrPerson.get(i).x-1, arrPerson.get(i).y-1, arrPerson.get(i).targetX-1, arrPerson.get(i).targetY-1);
                    
                    if (dist == -1) {
                        System.out.println(-1);
                        return;
                    }
                    
                    // 택시 위치를 도착지로 초기화 및 배열에서 손님 삭제
                    tX = arrPerson.get(i).targetX;
                    tY = arrPerson.get(i).targetY;
                    arrPerson.remove(i);
                    break;
                }
            }
                        
            K -= dist; // 손님에서 도착지까지의 거리
            
            // 기름이 없을 경우
            if (K < 0) {
                System.out.println(-1);
                return;
            }
            
            K += dist * 2; // 손님에서 도착지까지의 거리
        }
    }
    
    // 가까운 손님 찾기
    public static void findPerson(int x, int y, int dis) {
        boolean[][] visited = new boolean[N][N];
        PriorityQueue<Move> q = new PriorityQueue<>();
        q.add(new Move(x, y, dis));
        visited[x][y] = true;
        
        while (!q.isEmpty()) {
            Move now = q.poll();
            
            for (int i=0; i<arrPerson.size(); i++) {
                if (now.x == arrPerson.get(i).x-1 && now.y == arrPerson.get(i).y-1) {
                    nearPerson.add(new Move(now.x, now.y, now.dis));
                }
            }
            
            for (int i=0; i<4; i++) {
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];
                
                if (nx < 0 || ny < 0 || nx > N-1 || ny > N-1 || map[nx][ny] == 1 || visited[nx][ny]) continue;
                
                q.add(new Move(nx, ny, now.dis+1));
                visited[nx][ny] = true;
            }
        }
    }
    
    // 손님을 태우고 도착지까지 이동
    public static int goTaxi(int x, int y, int targetX, int targetY) {
        boolean[][] visited = new boolean[N][N];
        Queue<Move> q = new LinkedList<>();
        q.add(new Move(x, y, 0));
        
        while (!q.isEmpty()) {
            Move now = q.poll();
            
            if (now.x == targetX && now.y == targetY) {
                return now.dis;
            }
            
            for (int i=0; i<4; i++) {
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];
                
                if (nx < 0 || ny < 0 || nx > N-1 || ny > N-1 || map[nx][ny] == 1 || visited[nx][ny]) continue;
                
                q.add(new Move(nx, ny, now.dis+1));
                visited[nx][ny] = true;
            }
        }
        
        return -1;
    }
}