[백준] BOJ 19238 스타트 택시 (골드 2)

문제

---

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

19238번: 스타트 택시

---

해설

---

1. Map 자료구조 사용 (어떤 승객을 태울 것인지 찾기 위해 시간복잡도 이점을 위해)
   (승객의 출발지를 key, 목적지를 value로) Pair클래스의 equals, hashCode오버라이딩
   이때 x, y를 통해서만 비교하도록 오버라이딩 해준다. (breadth는 다를 수 있으므로)
2. bfs1()를 통해 현재 시작점에서 가장 가까운 승객을 찾는다.
   이때, 거리가 같은 승객을 행, 열로 처리해주기 위해서, 탐색 전 동일 너비를 처리해주도록 size를 사용
3. 너비가 같은 승객이 존재하면 행, 열을 비교하여 현재 승객을 선택한다.
   추가로 연료를 너비만큼 빼주고 start를 현재 승객 위치로 변경해준다.주의사항 : 승객을 선택했으면 맵에서 해당 승객을 제거해준다.
4. bfs2()를 통해 목적지까지의 너비를 구하고(equals로 목적지인지 비교), 너비만큼 연료에 더해준다.
5. 이를 총 승객 수만큼 반복해준다.

---

주의 사항

---

1. 처음에 Comparable을 통해 거리를 계산하고 pq에 넣어서 가장 가까운 것을 찾아서 그걸 승객 - 목적지로 설정
2. but 거리를 구할 때 벽을 고려하지 않아서 fail
3. 시작점에서 bfs를 통해 가장 가까운 승객을 찾음 : 너비를 저장해두고 너비만큼 돈다.
4. 너비만큼 돌면서 행, 열을 고려하여 우선으로 태울 승객을 찾고 나머지는 2, 3번 로직과 동일

---

코드 (시뮬레이션 + BFS)

---

import java.io.*;
import java.util.*;

public class Main {
    static int[][] map;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static Map<Pair, Pair> passengers;
    static int N, M, K;
    static Pair start;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

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

        st = new StringTokenizer(br.readLine());

        start = new Pair(Integer.parseInt(st.nextToken()) - 1, Integer.parseInt(st.nextToken()) - 1, 0);

        passengers = new HashMap<>();

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken()) - 1;
            int y = Integer.parseInt(st.nextToken()) - 1;
            int destX = Integer.parseInt(st.nextToken()) - 1;
            int destY = Integer.parseInt(st.nextToken()) - 1;
            passengers.put(new Pair(x, y, 0), new Pair(destX, destY, 0));
        }

        sb.append(solve());
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private static int solve() {
        while (!passengers.isEmpty()) {
            Pair dest = bfs1();
            if (dest == null) return -1;
            if (!bfs2(dest)) return -1;

        }
        return K;
    }

    private static boolean bfs2(Pair dest) {
        //승객에게 도착한 후 목적지로 이동 시키기
        boolean[][] isv = new boolean[N][N];
        Queue<Pair> queue = new ArrayDeque<>();
        queue.offer(new Pair(start.x, start.y, 0));
        isv[start.x][start.y] = true;
        if (start.x == dest.x && start.y == dest.y) return true;


        while (!queue.isEmpty()) {
            Pair p = queue.poll();

            if(K < p.breadth) return false;
            if (p.equals(dest)) {
                K += p.breadth;// K - (p.breadth + 1) + (2 * (p.breadth + 1));
                start = p;
                return true;
            }
            for (int i = 0; i < 4; i++) {
                int x = p.x + dx[i];
                int y = p.y + dy[i];

                if (x < 0 || x >= N || y < 0 || y >= N || isv[x][y] || map[x][y] == 1) continue;

                isv[x][y] = true;
                queue.offer(new Pair(x, y, p.breadth + 1));
            }
        }
        return false;
    }

    private static Pair bfs1() {
        boolean[][] isv = new boolean[N][N];
        Queue<Pair> queue = new ArrayDeque<>();
        queue.offer(new Pair(start.x, start.y, 0));
        isv[start.x][start.y] = true;

        int size = 0; //동일 너비 처리
        Pair passenger = null;
        Pair dest = null;
        Pair pass = passengers.get(new Pair(start.x, start.y, 0));
        if(pass != null) {
            dest = pass;
            passengers.remove(new Pair(start.x, start.y, 0));
            return dest;
        }
        while (!queue.isEmpty()) {
            size = queue.size();
            while (size-- > 0) {
                Pair p = queue.poll();

                if (K < p.breadth) return null;
                Pair check = passengers.get(p);
                if(check != null){
                    if (passenger == null) {
                        passenger = p;
                        dest = check;
                    } else {
                        if (passenger.x > p.x || (passenger.x == p.x && passenger.y > p.y)) {
                            passenger = p;
                            dest = check;
                        }
                    }
                }
                for (int i = 0; i < 4; i++) {
                    int x = p.x + dx[i];
                    int y = p.y + dy[i];

                    if (x < 0 || x >= N || y < 0 || y >= N || isv[x][y] || map[x][y] == 1) continue;

                    Pair passen = new Pair(x, y, p.breadth + 1);
                    isv[x][y] = true;
                    queue.offer(passen);
                }
            }
            if (passenger != null) {
                K -= passenger.breadth;
                passengers.remove(passenger);
                start.x = passenger.x;
                start.y = passenger.y;
                break;
            }
        }
        if(passenger == null) return null;
        return dest;
    }
}

class Pair {
    int x, y, breadth;

    public Pair(int x, int y, int breadth) {
        this.x = x;
        this.y = y;
        this.breadth = breadth;
    }
    
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Pair pair = (Pair) o;
        return x == pair.x && y == pair.y;
    }

    @Override
    public int hashCode() {
        return Objects.hash(x, y);
    }
}

---

결론

---

구현할 내용이 너무 많았던 문제

BFS시 동일 너비 처리를 해주어야 하는 점과, Map을 사용하며 equals, hashCode를 재정의 하는 등 

정말 많은 시간을 쏟아서 해결했던 문제 ㅠㅠ

---