이번에 풀어본 문제는
백준 19238번 스타트 택시 입니다.

📕 문제 링크

❗️코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Loc
{
    int x,y;
    int dist;

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

    public Loc(int x, int y, int dist)
    {
        this.x = x;
        this.y = y;
        this.dist = dist;
    }
}
public class Main {
    static int N,M,fuel;
    static Loc taxi;
    static boolean [][] visited;
    static int [][] map;
    static Loc [][] guest;
    static int end_cnt;
    static int [] dx = {-1,0,0,1};
    static int [] dy = {0,-1,1,0};
    static PriorityQueue<Loc> pq;
    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());
        fuel = Integer.parseInt(st.nextToken());

        map = new int[N+1][N+1];
        guest = new Loc[N+1][N+1];

        for(int i = 1; i <= N; ++i)
        {
            st = new StringTokenizer(br.readLine());
            for(int j = 1; j <= N; ++j)
            {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        //택시 시작위치
        st = new StringTokenizer(br.readLine());
        taxi = new Loc(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()));

        //손님 위치
        for(int i = 0; i < M; ++i)
        {
            st = new StringTokenizer(br.readLine());
            int start_x = Integer.parseInt(st.nextToken());
            int start_y = Integer.parseInt(st.nextToken());
            Loc start = new Loc(start_x,start_y);
            Loc end = new Loc(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()));

            guest[start_x][start_y] = getDistance(start,end);
            if(guest[start_x][start_y].dist == 0) // 애초에 도착지까지 못갈경우
            {
                System.out.print("-1");
                return;
            }
        }

        pq = new PriorityQueue<>(new Comparator<Loc>() {
            @Override
            public int compare(Loc o1, Loc o2) {
                if(o1.dist == o2.dist)
                {
                    if(o1.x == o2.x) return o1.y - o2.y;
                    return o1.x - o2.x;
                }
                return o1.dist - o2.dist;
            }
        });
        while(true)
        {
            if(end_cnt == M) break;
            if(!findGuest()) break;
        }

        if(end_cnt != M) fuel = -1;
        System.out.print(fuel);
    }
    static Loc getDistance(Loc start, Loc end)
    {
        Queue<Loc> q = new LinkedList<>();
        visited = new boolean[N+1][N+1];
        visited[start.x][start.y] = true;
        q.add(new Loc(start.x,start.y,0));

        while(!q.isEmpty())
        {
            Loc cur = q.poll();

            if(cur.x == end.x && cur.y == end.y)
            {
                return cur;
            }
            for(int idx = 0; idx < 4; ++idx)
            {
                int mx = cur.x + dx[idx];
                int my = cur.y + dy[idx];

                if(!isValid(mx,my) || visited[mx][my] || map[mx][my] > 0) continue;
                visited[mx][my] = true;
                q.add(new Loc(mx,my,cur.dist+1));
            }
        }
        return new Loc(0,0);
    }
    static boolean findGuest()
    {
        Queue<Loc> q = new LinkedList<>();
        visited = new boolean[N+1][N+1];
        visited[taxi.x][taxi.y] = true;
        q.add(new Loc(taxi.x,taxi.y,0));

        int tmp_dist = Integer.MAX_VALUE;
        while(!q.isEmpty())
        {
            Loc cur = q.poll();

            if(cur.dist > tmp_dist) break;
            if(guest[cur.x][cur.y] != null)
            {
                tmp_dist = cur.dist;
                pq.add(new Loc(cur.x,cur.y,cur.dist));
                continue;
            }
            for(int idx = 0; idx < 4; ++idx)
            {
                int mx = cur.x + dx[idx];
                int my = cur.y + dy[idx];

                if(!isValid(mx,my) || visited[mx][my] || map[mx][my] > 0) continue;
                visited[mx][my] = true;
                q.add(new Loc(mx,my,cur.dist+1));
            }
        }
        if(!pq.isEmpty())
        {
            Loc start = pq.poll();
            Loc end = guest[start.x][start.y];

            taxi.x = end.x;
            taxi.y = end.y;

            fuel -= (start.dist + end.dist); // taxi -> guest -> dest

            if(fuel < 0) return false;

            fuel += (end.dist * 2);
            end_cnt++;
            guest[start.x][start.y] = null;
            pq.clear();
            return true;
        }
        return false;
    }
    static boolean isValid(int x, int y)
    {
        return x > 0 && y > 0 && x <= N && y <= N;
    }
}

📝 풀이

택시의 출발지점과 승객들의 위치, 초기연료값이 주어집니다.
입력된 출발지점 부터 시작합니다. 택시는 현재 위치에서 가장 가까운 승객을 태워, 해당 승객의 목적지로 이동시켜줍니다. 이 과정에서 한칸당 1의 연료를 소모하고, 중간에 연료가 부족할 경우 -1을 출력하고 종료합니다. 승객을 태워 도착지점에 도착했을 경우, 승객을 태운 위치에서 목적지 까지 소모한 연료의 2배 값을 충전받게 됩니다.
우선 승객의 위치와 목적지, 그리고 목적지 까지의 거리는 변하지 않는 값이기 때문에 입력받음과 동시에 getDistance함수를 통해 구해줍니다.
guest 배열의 인덱스에 값이 존재한다면, 그 위치에 승객이 존재하며 해당 인덱스의 값은 목적지의 좌표와 목적지 까지의 거리가 담겨 있습니다.
이를 활용하여 while문 내에서 현재 택시의 위치를 기준으로 findGuest를 반복 수행할 때 마다, 가장 가까운 승객을 찾아 bfs연산을 수행하고, 우선순위 큐에 승객의 x,y좌표와 승객까지의 거리를 담고 조건에 가장 부합하는 승객을 태웁니다. guest배열의 값으로 목적지 까지의 정보를 모두 얻을 수 있기 때문에, 즉시 연료 값에 대한 연산을 수행해 주고, 연료가 음수가 될경우 바로 false를 리턴, 그렇지 않다면 다음 반복으로 돌아가 다시 findGuest 함수를 수행하게 됩니다.
모든 반복이 끝났을 때, end_cnt값이 M값과 다르다면 모든 승객을 태우지 못한 상태이기 때문에 -1을, 그렇지 않다면 현재 fuel값을 그대로 출력하면 됩니다.

📜 후기

dx,dy의 값을 상,좌,우,하 순서로 배치하면 따로 비교연산을 하지 않아도 최적의 승객을 태울 수 있을 것이라고 예상했었는데, 게시판의 왠만한 테스트케이스를 다 통과함에도 제출하면 7%에서 틀렸다고 나오네요..
어쩔 수 없이 우선순위 큐를 추가로 사용하여 조금 번거롭더라도 확실한 조건의 승객을 태울 수 있도록 바꿔보았는데, 반례가 뭔지는 조금 궁금하긴 하네요 ㅠㅠ
문제는 엄청 재밌어요! 풀어보십셔~.~