[백준] G2 19238 스타트택시 (java)

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

19238번: 스타트 택시

 

 

풀이

 

0) 변수 설정
  N : map의 크기
  fuel : 연료
  map : 지도 (N by N)
  tr, tc : 택시의 위치
  distanceMap[r][c] : 현재 택시 위치에서 (r,c) 까지의 거리. 못 가는 경우가 있으므로 -1로 초기화 한다.
  isVisited[r][c] : (r,c) 위치를 방문했는지 체크

1) 입력값을 담을 Passenger 클래스를 생성한다. 
  1-1) Passenger 클래스의 인스턴스는
      sr : 승객의 행 위치
      sc : 승객의 행 위치
      er : 목적지의 행 위치
      ec : 목적지의 열 위치 
      distanceFromTaxi : 택시의 현재 위치에서 승객까지 거리
      distanceFromDestination : 승객의 위치에서 목적지까지 거리
 1-2) Comparable 인터페이스를 구현한다. 우선순위는 distanceFromTaxi > sr >  sc 이다

2) List<Passenger>에 input값을 넣자. 여기서 distanceFromDestination 은 고정된 값이다.
  2-1) bfs로 (sr,sc) 에서 (er,ec) 까지의 이동거리 값을 리턴하는 getDistance(sr,sc,er,ec)를 만든다.
  2-2) 이때 벽에 막혀 목적지까지 이동을 못할 수도 있다. 그땐 -1을 리턴하자.
  2-3) -1이 리턴되면 그냥 -1을 출력 후 리턴한다.

3) 이제 distanceFromTaxi를 구해야한다.
  3-1) List를 순회하며 각각의 승객과 택시와의 거리를 bfs로 일일이 계산하면 시간초과가 난다. 
  3-2) 따라서 현재 택시 위치 (tr,tc) 에서 모든 좌표까지의 거리를 bfs 한번만 수행하여 distanceMap[][]을 초기화 해야한다. 
  3-3) setDistanceMap()을 통해 distanceMap[][] 을 세팅 후, List를 순회하여 distanceFromTaxi를 초기화 한다.
  3-4) 물론 이때도 벽에 막혀 도달할 수 없는 경우라면 -1을 출력하고 리턴한다.

4) distanceFromTaxi가 설정 되었으니 Collections.sort()를 통해 우선순위별로 정렬한다.

5) 이제 택시는 최우선 순위의 승객인 0번 인덱스의 Passenger를 태우러 가야한다.

6) 택시가 승객을 태우고 목적지까지 갈 수 있는지 계산한다.
  택시 to 승객 : distanceFromTaxi
  승객 to 목적지 : distanceFromDestination
  남은연료 : fuel
  6-1) fuel < distanceFromTaxi + distanceFromDestination 이면 연료 부족으로 이동할 수 없다. -1 출력 후 리턴한다.
  6-2) 그 외의 경우는 이동이 가능하다. 조건에 맞게 연료와 택시의 좌표를 갱신한다.
          fuel = fuel - distanceFromTaxi + distanceFromDestination
          tr, tc = 승객의 목적지 (er, ec)
  6-3) 승객을 목적지까지 정상적으로 운송하면 해당 승객을 List에서 remove 한다.
  6-4) 더 이상 운송할 승객이 없거나 연료가 다 닳때 까지 3번 ~ 6번을 반복한다.

7) 남은 연료 fuel을 출력한다.

 

 

주의사항

 

1) List를 순회하며 각각의 승객과 택시와의 거리를 bfs로 일일이 계산하면 시간초과가 난다. 

 

package com.baekJoon;

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

public class BJ_G2_19238_스타트택시 {
    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer tokens;
    static int N, map[][], distanceMap[][];
    static boolean isVisited[][];
    static List<Passenger> passengers = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        input = new BufferedReader(new StringReader(src));
        tokens = new StringTokenizer(input.readLine());
        N = Integer.parseInt(tokens.nextToken());
        int M = Integer.parseInt(tokens.nextToken());
        int fuel = Integer.parseInt(tokens.nextToken());

        map = new int[N][N];
        distanceMap = new int[N][N];

        for(int r=0; r<N; r++){
            tokens = new StringTokenizer(input.readLine());
            for(int c=0; c<N; c++){
                map[r][c] = Integer.parseInt(tokens.nextToken());
            }
        }
        tokens = new StringTokenizer(input.readLine());
        int tr = Integer.parseInt(tokens.nextToken())-1;
        int tc = Integer.parseInt(tokens.nextToken())-1;

        for(int i=0; i<M; i++){
            tokens = new StringTokenizer(input.readLine());
            int sr = Integer.parseInt(tokens.nextToken())-1;
            int sc = Integer.parseInt(tokens.nextToken())-1;
            int er = Integer.parseInt(tokens.nextToken())-1;
            int ec = Integer.parseInt(tokens.nextToken())-1;
            int distanceFromDestination = getDistance(sr,sc,er,ec);
            if(distanceFromDestination == -1){
                System.out.println(-1);
                return;
            }
            passengers.add(new Passenger(sr,sc,er,ec, 0, distanceFromDestination));
        }

        while(fuel > 0 && passengers.size()> 0){
            setDistanceMap(tr, tc);
            for(int i=0; i<passengers.size(); i++){
                passengers.get(i).distanceFromTaxi = distanceMap[passengers.get(i).sr][passengers.get(i).sc];
                if(passengers.get(i).distanceFromTaxi == -1){
                    System.out.println(-1);
                    return;
                }
            }
            Collections.sort(passengers);

            if(fuel>=passengers.get(0).distanceFromTaxi + passengers.get(0).distanceFromDestination){
                fuel = fuel - passengers.get(0).distanceFromTaxi + passengers.get(0).distanceFromDestination;
                tr = passengers.get(0).er;
                tc = passengers.get(0).ec;
                passengers.remove(0);
            }else{
                System.out.println(-1);
                return;
            }
        }
        System.out.println(fuel);
    }

    private static void setDistanceMap(int sr, int sc) {
        for(int r=0; r<N; r++){
            for(int c=0; c<N; c++){
                distanceMap[r][c] = -1;
            }
        }
        isVisited = new boolean[N][N];
        Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node(sr,sc,0));
        isVisited[sr][sc] = true;

        while (!queue.isEmpty()){
            Node front = queue.poll();
            distanceMap[front.r][front.c] = front.d;
            for(int d=0; d<4; d++){
                int nr = front.r + dr[d];
                int nc = front.c + dc[d];
                
                if(isIn(nr,nc) && !isVisited[nr][nc] && map[nr][nc] == 0){
                    isVisited[nr][nc] = true;
                    queue.offer(new Node(nr, nc, front.d+1));
                }
            }
        }
    }

    private static int getDistance(int sr, int sc, int er, int ec) {
        isVisited = new boolean[N][N];
        Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node(sr, sc, 0));
        isVisited[sr][sc] = true;

        while (!queue.isEmpty()){
            Node front = queue.poll();
            if(front.r == er && front.c == ec){
                return front.d;
            }
            for(int d=0; d<4; d++){
                int nr = front.r + dr[d];
                int nc = front.c + dc[d];

                if(isIn(nr,nc) && !isVisited[nr][nc] && map[nr][nc] == 0){
                    queue.offer(new Node(nr,nc, front.d+1));
                    isVisited[nr][nc] = true;
                }
            }
        }
        return -1; // 벽에 막혔나벼
    }


    static int dr[] = {0,0,-1,1};
    static int dc[] = {-1,1,0,0};
    
    static boolean isIn(int r, int c){
        return (r>=0 && c>=0 && r<N && c<N);
    }
    
    static class Node{
        int r;
        int c;
        int d;

        public Node(int r, int c, int d) {
            this.r = r;
            this.c = c;
            this.d = d;
        }
    }

    static class Passenger implements Comparable<Passenger>{
        int sr;
        int sc;
        int er;
        int ec;
        int distanceFromTaxi;
        int distanceFromDestination;

        public Passenger(int sr, int sc, int er, int ec, int distanceFromTaxi, int distanceFromDestination) {
            this.sr = sr;
            this.sc = sc;
            this.er = er;
            this.ec = ec;
            this.distanceFromTaxi = distanceFromTaxi;
            this.distanceFromDestination = distanceFromDestination;
        }

        @Override
        public int compareTo(Passenger o) {
            if(this.distanceFromTaxi == o.distanceFromTaxi){
                if(this.sr == o.sr){
                    return Integer.compare(this.sc, o.sc);
                }
                return Integer.compare(this.sr, o.sr);
            }
            return Integer.compare(this.distanceFromTaxi, o.distanceFromTaxi);
        }
    }

    static String src =
            "6 3 100\n" +
                    "0 0 1 0 0 0\n" +
                    "0 0 1 0 0 0\n" +
                    "0 0 0 1 0 0\n" +
                    "0 0 0 1 0 0\n" +
                    "0 0 0 0 1 0\n" +
                    "0 0 0 1 0 0\n" +
                    "6 5\n" +
                    "2 2 5 6\n" +
                    "5 4 1 6\n" +
                    "4 2 3 5";
}

 

 

 

후기

 

 1년 전에 풀때는 "틀렸습니다" 이지만 이번에는 "시간초과"가 났다.

1년 전 소스를 다시 봤는데 이건 뭐.. 풀이도 그지같고 가독성도 구려서 내가 봐도 이해가 안간다.

비록 시간 초과때문에 약간 헤매었지만 로직 자체는 전 보다 훨씬 깔끔하게 짠것 같아서 성장한 기분이다.

1년 후에 지금의 소스를 다시 본다면 아마 이해할 수 있을것 같다.