[백준 19238] 스타트 택시 -JAVA //le_effort

스타트 택시

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초 (추가 시간 없음)	512 MB	546	108	78	23.009%

문제

스타트링크가 "스타트 택시"라는 이름의 택시 사업을 시작했다. 스타트 택시는 특이하게도 손님을 도착지로 데려다줄 때마다 연료가 충전되고, 연료가 바닥나면 그 날의 업무가 끝난다.

택시 기사 최백준은 오늘 M명의 승객을 태우는 것이 목표이다. 백준이 활동할 영역은 N×N 크기의 격자로 나타낼 수 있고, 각 칸은 비어 있거나 벽이 놓여 있다. 택시가 빈칸에 있을 때, 상하좌우로 인접한 빈칸 중 하나로 이동할 수 있다. 알고리즘 경력이 많은 백준은 특정 위치로 이동할 때 항상 최단경로로만 이동한다.

M명의 승객은 빈칸 중 하나에 서 있으며, 다른 빈칸 중 하나로 이동하려고 한다. 여러 승객이 같이 탑승하는 경우는 없다. 따라서 백준은 한 승객을 태워 목적지로 이동시키는 일을 M번 반복해야 한다. 각 승객은 스스로 움직이지 않으며, 출발지에서만 택시에 탈 수 있고, 목적지에서만 택시에서 내릴 수 있다.

백준이 태울 승객을 고를 때는 현재 위치에서 최단거리가 가장 짧은 승객을 고른다. 그런 승객이 여러 명이면 그중 행 번호가 가장 작은 승객을, 그런 승객도 여러 명이면 그중 열 번호가 가장 작은 승객을 고른다. 택시와 승객이 같은 위치에 서 있으면 그 승객까지의 최단거리는 0이다. 연료는 한 칸 이동할 때마다 1만큼 소모된다. 한 승객을 목적지로 성공적으로 이동시키면, 그 승객을 태워 이동하면서 소모한 연료 양의 두 배가 충전된다. 이동하는 도중에 연료가 바닥나면 이동에 실패하고, 그 날의 업무가 끝난다. 승객을 목적지로 이동시킨 동시에 연료가 바닥나는 경우는 실패한 것으로 간주하지 않는다.

<그림 1>

<그림 1>은 택시가 활동할 영역의 지도를 나타내며, 택시와 세 명의 승객의 출발지와 목적지가 표시되어 있다. 택시의 현재 연료 양은 15이다. 현재 택시에서 각 손님까지의 최단거리는 각각 9, 6, 7이므로, 택시는 2번 승객의 출발지로 이동한다.

<그림 2>	<그림 3>

<그림 2>는 택시가 2번 승객의 출발지로 가는 경로를, <그림 3>은 2번 승객의 출발지에서 목적지로 가는 경로를 나타낸다. 목적지로 이동할 때까지 소비한 연료는 6이고, 이동하고 나서 12가 충전되므로 남은 연료의 양은 15이다. 이제 택시에서 각 손님까지의 최단거리는 둘 다 7이므로, 택시는 둘 중 행 번호가 더 작은 1번 승객의 출발지로 이동한다.

<그림 4>	<그림 5>

<그림 4>와 <그림 5>는 택시가 1번 승객을 태워 목적지로 이동시키는 경로를 나타낸다. 남은 연료의 양은 15 - 7 - 7 + 7×2 = 15이다.

<그림 6>	<그림 7>

<그림 6>과 <그림 7>은 택시가 3번 승객을 태워 목적지로 이동시키는 경로를 나타낸다. 최종적으로 남은 연료의 양은 15 - 5 - 4 + 4×2 = 14이다.

모든 승객을 성공적으로 데려다줄 수 있는지 알아내고, 데려다줄 수 있을 경우 최종적으로 남는 연료의 양을 출력하는 프로그램을 작성하시오.

입력

첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다.

다음 줄부터 N개의 줄에 걸쳐 백준이 활동할 영역의 지도가 주어진다. 0은 빈칸, 1은 벽을 나타낸다.

다음 줄에는 백준이 운전을 시작하는 칸의 행 번호와 열 번호가 주어진다. 행과 열 번호는 1 이상 N 이하의 자연수이고, 운전을 시작하는 칸은 빈칸이다.

그다음 줄부터 M개의 줄에 걸쳐 각 승객의 출발지의 행과 열 번호, 그리고 목적지의 행과 열 번호가 주어진다. 모든 출발지와 목적지는 빈칸이고, 모든 출발지는 서로 다르며, 각 손님의 출발지와 목적지는 다르다.

출력

모든 손님을 이동시키고 연료를 충전했을 때 남은 연료의 양을 출력한다. 단, 이동 도중에 연료가 바닥나서 다음 출발지나 목적지로 이동할 수 없으면 -1을 출력한다. 모든 손님을 이동시킬 수 없는 경우에도 -1을 출력한다.

예제 입력 1 복사

xxxxxxxxxx
6 3 15
0 0 1 0 0 0
0 0 1 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 1 0
0 0 0 1 0 0
6 5
2 2 5 6
5 4 1 6
4 2 3 5

예제 출력 1 복사

xxxxxxxxxx
14

예제 입력 2 복사

xxxxxxxxxx
6 3 13
0 0 1 0 0 0
0 0 1 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 1 0
0 0 0 1 0 0
6 5
2 2 5 6
5 4 1 6
4 2 3 5

예제 출력 2 복사

xxxxxxxxxx
-1

예제 입력 3 복사

xxxxxxxxxx
6 3 100
0 0 1 0 0 0
0 0 1 0 0 0
0 0 0 1 0 0
0 0 0 1 0 0
0 0 0 0 1 0
0 0 0 1 0 0
6 5
2 2 5 6
5 4 1 6
4 2 3 5

예제 출력 3 복사

-1

 

 

풀이

2020년 상반기 삼성전자 SET 부분 기출 문제

일단 맵의 출발지에다가 맵에 번호를 매겨 두었다.

우선 기존의 장애물인 1은 -1로 바꿔두었다

이유) 1부터 번호를 매길 것인데 장애물 1로 겹치니까

 

 

 

1. 가장 거리가 가까운, 거리가 가깝다면 행, 열을 기준으로 태울 손님 찾기.

    

class Node implements Comparable<Node>{
    int x,y,dist;
    Node(int x, int y, int dist){
        this.x=x;
        this.y=y;
        this.dist=dist;
    }
    public int compareTo(Node o) {
        if(this.dist!=o.dist) {
            return this.dist-o.dist;
        }
        else {
            if(this.x != o.x) {
                return this.x-o.x;
            }
            else {
                return this.y-o.y;
            }
        }
    }
}

정렬로 3가지 조건을 한 번에 해결했다.

 

1-1 예외) 맵을 탐색하면서 벽에 의해서 못가면 -1 출력하고 끝내기

 

2. 현재 위치에서 태울 손님 위치로 이동한 만큼의 연료 빼기

   2-1 예외) 연료가 부족하면 -1 출력하고 끝내기

 

3. 승객의 위치에서 승객의 목적지까지 가기

   3-1 예외) 벽에 의해서 못가거나 연료가 부족하면 -1출력후 끝내기

 

4. 연료를 2배 더해주기

 

 

전체코드

import java.io.*;
import java.util.*;
public class Main {
    static int n,m,fuel;
    static int map[][];
    static boolean visited[][];
    static int driver_x,driver_y;
    static int dx[] = {0,0,1,-1};
    static int dy[] = {1,-1,0,0};
    static ArrayList<Node>guest = new ArrayList<>();
    static ArrayList<Info>cust_list = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String[] t = br.readLine().split(" ");
        n = Integer.parseInt(t[0]);
        m = Integer.parseInt(t[1]);
        fuel = Integer.parseInt(t[2]);
        
        map = new int[n+1][n+1];
        visited = new boolean[n+1][n+1];
        
        for(int i=1; i<=n; i++) {
            String[] map_input = br.readLine().split(" ");
            for(int j=1; j<=n; j++) {
                map[i][j] = Integer.parseInt(map_input[j-1]);
                if(map[i][j]==1) {
                    map[i][j]=-1;
                }
            }
        }
        String[] tt = br.readLine().split(" ");
        driver_x = Integer.parseInt(tt[0]);
        driver_y = Integer.parseInt(tt[1]);
        
        for(int i=0; i<m; i++) {
            String[] a = br.readLine().split(" ");
            int start_x = Integer.parseInt(a[0]);
            int start_y = Integer.parseInt(a[1]);
            int end_x = Integer.parseInt(a[2]);
            int end_y = Integer.parseInt(a[3]);
            cust_list.add(new Info(start_x,start_y,end_x,end_y));
            map[start_x][start_y] = i+1;
        }
        while(true) {
            
            if(cust_list.size()==0) {
                System.out.println(fuel);
                return;
            }
            guest.clear();
            visited = new boolean[n+1][n+1];
            get_cust(driver_x,driver_y);    //가장 가까운 손님 찾기
            if(guest.size()==0) {               //벽에 의해서 못가거나 이런경우 (승객을 못태울 경우)
                System.out.println(-1);
                return ;
            }
            Node a = guest.get(0);
            map[a.x][a.y] = 0;
            fuel-=a.dist;   // 기사 현재위치에서 승객을 데리러 가는 연료 소비
            if(fuel<0) {            // 연료가 없으면 끝
                System.out.println(-1);
                return ;
            }
            int dist = 0;
            //승객의 위치에서 승객의 목적지까지 가는 과정
            visited = new boolean[n+1][n+1];
            for(int i=0; i<cust_list.size(); i++) {
                Info info = cust_list.get(i);
                if(info.start_x == a.x && info.start_y == a.y) {
                    dist = get_dist(info.start_x,info.start_y,info.end_x,info.end_y);
                        if(dist == -1) {
                            System.out.println(-1);
                            return;
                        }
                        driver_x = info.end_x;
                        driver_y = info.end_y;
                        cust_list.remove(info);
                        break;
                    }
                }
            fuel-=dist;
            if(fuel<0) {
                System.out.println(-1);
                return ;
            }
            fuel+=dist*2;
            }
        }
    public static int get_dist(int x, int y,int end_x, int end_y) {
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(x,y,0));
        while(!q.isEmpty()) {
            Node a= q.poll();
            if(a.x == end_x && a.y== end_y) {
                return a.dist;
            }
            for(int i=0; i<4; i++) {
                int nx = a.x+dx[i];
                int ny = a.y+dy[i];
                if(isRange(nx,ny) && !visited[nx][ny] && map[nx][ny]!=-1) {
                    visited[nx][ny] = true;
                    q.add(new Node(nx,ny,a.dist+1));
                }
            }
        }
        return -1;
    }
    public static void get_cust(int x, int y) {
        PriorityQueue<Node> q = new PriorityQueue<>();
        q.add(new Node(x,y,0));
        
        while(!q.isEmpty()) {
            Node a= q.poll();
            if(map[a.x][a.y]>=1) {
                guest.add(new Node(a.x,a.y,a.dist));
                break;
            }
            for(int i=0; i<4; i++) {
                int nx = a.x+dx[i];
                int ny = a.y+dy[i];
                if(isRange(nx,ny) && map[nx][ny]!=-1 && !visited[nx][ny]) {
                    visited[nx][ny] = true;
                    q.add(new Node(nx,ny,a.dist+1));
                }
            }
        }
    }
    public static boolean isRange(int x, int y) {
        if(x>=1 && y>=1 && x<=n && y<=n) {
            return true;
        }
        return false;
    }
}
class Info{
    int start_x,start_y,end_x,end_y;
    Info(int start_x, int start_y, int end_x, int end_y){
        this.start_x = start_x;
        this.start_y= start_y;
        this.end_x = end_x;
        this.end_y = end_y;
    }
}
class Node implements Comparable<Node>{
    int x,y,dist;
    Node(int x, int y, int dist){
        this.x=x;
        this.y=y;
        this.dist=dist;
    }
    public int compareTo(Node o) {
        if(this.dist!=o.dist) {
            return this.dist-o.dist;
        }
        else {
            if(this.x != o.x) {
                return this.x-o.x;
            }
            else {
                return this.y-o.y;
            }
        }
    }
}