백준 19238 (스타트 택시) java

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

19238번: 스타트 택시

 

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

public class Main {
    /*
    * 백준 19238 스타트 택시
    * 유형 : 그래프 탐색 , bfs
    * 움직이는 대상 : 택시 -> 상하좌우 이동
    * 승객을 고르는 방법 : 현재 위치에서 최단 거리가 가장 짧은 승객 ( 탐색 )
    * 최단 거리가 같은 경우 : 행번호 작은 거 우선, 열번호 작은거
    * 연료 : 한칸 이동시 1만큼 소요 , 목적지 도착시 이동 거리 * 2 충전
    *
    * (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000)
     * */
    static int n = 0; // 행,열
    static int m = 0; // 승객 수

    static int oil = 0;
    static point start;
    static int[][] board = new int[22][22];
    static int[] dx = {0,0,-1,1};
    static int[] dy = {1,-1,0,0};
    static HashMap<Integer,point> goal = new HashMap<>();
    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());
        oil = Integer.parseInt(st.nextToken());

        for(int i=1;i<=n;i++)
        {
            st = new StringTokenizer(br.readLine()," ");
            for(int j=1;j<=n;j++)
            {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        st = new StringTokenizer(br.readLine()," ");
        start = new point(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()));

        for(int i=1;i<=m;i++)
        {
            st = new StringTokenizer(br.readLine()," ");
            int sx = Integer.parseInt(st.nextToken());
            int sy = Integer.parseInt(st.nextToken());
            int lx = Integer.parseInt(st.nextToken());
            int ly = Integer.parseInt(st.nextToken());

            board[sx][sy]=i+1;
            point last = new point(lx,ly);
            goal.put(i+1,last);
        }
        int result = 0;
        for(int i=1;i<=m;i++)
        {
            result = bfs();
            if(result==-1)
            {
                break;
            }
        }
        if(result==-1)
        {
            System.out.println(-1);
        }
        else {
            System.out.println(oil);
        }
        br.close();
    }
    static int bfs()
    {
        Queue<point> q= new LinkedList<>();
        int rx = 22;
        int ry = 22;
        int rd = 501;
        int[][] visit = new int[22][22];
        q.add(start);
        visit[start.x][start.y] = 1;

        while(!q.isEmpty())
        {
            point cur = q.poll();
            if(board[cur.x][cur.y]>1)
            {
                if(rd>visit[cur.x][cur.y]-1)
                {
                    rx = cur.x;
                    ry = cur.y;
                    rd = visit[cur.x][cur.y]-1;
                }

                else if(rd==visit[cur.x][cur.y]-1)
                {
                    if(rx>cur.x)
                    {
                        rx = cur.x;
                        ry = cur.y;
                        rd = visit[cur.x][cur.y]-1;
                    }
                    else if(rx==cur.x)
                    {
                        if(ry>cur.y)
                        {
                            rx = cur.x;
                            ry = cur.y;
                            rd = visit[cur.x][cur.y]-1;
                        }
                    }
                }
            }
            for(int i=0;i<4;i++)
            {
                int nx= cur.x+dx[i];
                int ny = cur.y+dy[i];

                if(nx>=1&&nx<=n&&ny>=1&&ny<=n)
                {
                    if(board[nx][ny]!=1&&visit[nx][ny]==0)
                    {
                        visit[nx][ny]= visit[cur.x][cur.y]+1;
                        q.add(new point(nx,ny));
                    }
                }
            }
        }
        if(rx==22||ry==22||rd==501)
        {
            return -1;
        }
        if(oil-rd<=0)
        {
            return -1;
        }
        oil = oil - rd;
        point des = goal.get(board[rx][ry]);
        board[rx][ry]=0;
        visit = new int[22][22];
        q.add(new point(rx,ry));
        visit[rx][ry]=1;
        while(!q.isEmpty())
        {
            point cur = q.poll();

            for(int i=0;i<4;i++) {
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];

                if (nx >= 1 && nx <= n && ny >= 1 && ny <= n) {
                    if(visit[nx][ny]==0&&board[nx][ny]!=1)
                    {
                        visit[nx][ny]= visit[cur.x][cur.y]+1;
                        if(oil-(visit[nx][ny]-1)<0)
                        {
                            return -1;
                        }
                        q.add(new point(nx,ny));
                    }
                    if(nx==des.x&&ny==des.y)
                    {
                        oil = oil + (visit[nx][ny]-1);
                        start = new point(nx,ny);
                        return visit[nx][ny]-1;
                    }
                }
            }
        }

        return -1;
    }

}
class point
{
    int x;
    int y;
    point(int x,int y)
    {
        this.x = x;
        this.y = y;
    }
}

해당 문제는 기본적으로 한 명의 승객을 목적지로 도달시키기 위해 2번의 bfs 탐색이 필요하다. 첫 번째로 가장 거리가 가까운 승객을 찾는 탐색과 해당 승객을 해당 목적지로 도달시키는 작업 !

goal 이라는 HashMap을 사용하여 승객의 목적지 정보를 유지한다. 이런 작업을 하는 이유는 기본적으로 승객의 목적지는 겹칠수 있기 때문이다.

 

코드가 길다!!