BOJ 백준 19238 스타트 택시 [JAVA]

 

[ 문제 해설 ]

• N*N 격자 칸에서 M 명의 승객을 태워 목적지에 데려다줍니다. 각 칸은 비어 있거나 벽이 놓여있습니다.
• 손님을 같이 태우는 일은 없습니다. 승객을 태워 목적지로 이동시키는 일을 M 번 반복합니다.
• 손님은 출발지에서만 택시에 타고 도착지에서만 내립니다.
• 승객을 태울 때는 현재 위치에서 최단거리가 가장 짧은 승객을 태웁니다. 그런 승객이 여러 명이면 그중 행번호가 가장 작은 승객을, 이것도 여러 명이면 열 번호가 가장 작은 승객을 태웁니다.
• 택시와 승객이 같은 위치에 있다면 최단거리는 0입니다.
• 연료는 한 칸 이동 시마다 1만큼 소모되며 한 승객을 목적지로 성공적으로 이동시키면, 그 승객을 태워 이동하면서 소모한 연료 양의 두 배가 충전됩니다.
• 이동 중 연료가 바닥나면 이동에 실패하고 업무가 끝납니다. 승객을 목적지로 이동시킨 동시에 연료가 바닥나는 경우는 실패한 것으로 간주하지 않습니다.
• 연료는 무한히 담을 수 있습니다.
• 모든 출발지와 목적지는 빈칸이고, 모든 출발지는 서로 다르고, 각 손님 당 그 사람의 출발과 목적지는 다릅니다.
• 모든 승객을 성공적으로 데려다줄 수 있는지 알아내고, 데려다줄 수 있다면 최종적으로 남는 연료의 양을 출력합니다.
• 이동 중 연료 바닥 시 -1을 출력하고 종료합니다.

 

[ 테스트 케이스 설명 ]

6 2 2 // 지도 크기(2<=20), 손님 수(1<=지도크기^2), 연료의 양(1<=500,000)
0 0 1 0 0 0// 0은 빈칸 1은 벽을 나타냄
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 // 운전을 시작하는 행, 열번호가 주어짐(1<=N)
6 6 5 6 // 승객 출발지 행과 열번호, 목적지의 행과 열번호가 주어짐
4 6 4 5
답 : 2

 

[ 알고리즘 분류 ]

• 구현
• 그래프 이론
• 그래프 탐색
• 시뮬레이션
• 너비 우선 탐색
• 격자 그래프

 

[ 문제 해설 ]

 

BFS를 활용한 구현 문제입니다.

 

[택시의 현 위치에서 손님까지 이동] 함수와 [현 위치에서 손님의 목적지 가지 이동] 함수만 잘 구현하면 됩니다.

 

현 위치에서 가장 가까운 손님까지 이동할 때, Y좌표 기준 작은 것, X좌표 기준 작은 것 순으로 접근해야 하기 때문에 이 부분만 신경 써서 구현해 주면 됩니다.

 

그리고 현 위치에서 손님의 목적지까지 간 후, 연료 데이터 갱신 시 2배 해주어야 하는데, 현 위치에서 목적지까지 간 연로도 생각해야 하니 결국 거리만큼만 연료에 더해주면 됩니다.

 

[ 정답 코드 ]

import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.util.ArrayDeque;

class Main{
	
	static final int dxy[][] = {{-1,0},{0,-1},{1,0},{0,1}};
	static boolean[][] isWall, visit, customer;
	static int [][]destinationY, destinationX;
	
	static ArrayDeque<Pos> q;
	static int y, x, gy, gx;
	static int N, M, F;
	
	public static void main(String[] args)throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());// 지도 크기(2<=20)
		M = Integer.parseInt(st.nextToken());// 손님 수(1<=지도크기^2)
		F = Integer.parseInt(st.nextToken());// 연료의 양(1<=500,000)
		q = new ArrayDeque<>();
		isWall = new boolean[N + 2][N + 2];
		visit = new boolean[N + 2][N + 2];
		customer = new boolean[N + 2][N + 2]; // 손님이 있는 위치
		destinationY = new int[N + 2][N + 2];// 각 손님의 도착 행과 열번호 저장
		destinationX = new int[N + 2][N + 2];// 각 손님의 도착 행과 열번호 저장
		
		for(int i=0; i< N + 2; i++)
			isWall[i][N + 1] = isWall[N + 1][i] = isWall[0][i] = isWall[i][0] = true;
		
		for(int y=1; y<=N; y++)
		{
			st = new StringTokenizer(br.readLine());
			for(int x=1; x<=N; x++)
				isWall[y][x] = "1".equals(st.nextToken());// 벽이면 true
		}
		
		st = new StringTokenizer(br.readLine());
		y = Integer.parseInt(st.nextToken());// 운전을 시작하는 행, 열번호가 주어짐(1<=N)
		x = Integer.parseInt(st.nextToken());// 운전을 시작하는 행, 열번호가 주어짐(1<=N)
		
		for(int i=1; i<=M; i++)
		{
			st = new StringTokenizer(br.readLine());
			int sy = Integer.parseInt(st.nextToken());// 승객 출발지 행번호
			int sx = Integer.parseInt(st.nextToken());// 승객 출발지 열번호
			int ey = Integer.parseInt(st.nextToken());// 목적지의 행번호
			int ex = Integer.parseInt(st.nextToken());// 목적지의 열번호
			
			customer[sy][sx] = true;// 승객의 출발지에 마킹
			destinationY[sy][sx] = ey;// 손님 시작점에 종료 행 번호입력
			destinationX[sy][sx] = ex;// 손님 시작점에 종료 열 번호입력
		}
		
		while(M-->0)// 손님수만큼 반복
		{
			// 택시가 손님에게로 이동, 택시가 목적지로 이동 중 하나라도 안되면 -1 종료
			if(!moveToPassenger() || !moveToDestination())
			{
				F = -1;
				break;
			}
		}
		
		System.out.print(F);
	}
	static boolean moveToDestination() {
		// 현 택시 위치에서 손님의 목적지까지 최단거리로 이동한다.
		clear();
		q.add(new Pos(y, x, 0));
		visit[y][x] = true;
		
		while(!q.isEmpty())
		{
			Pos now = q.poll();
			
			if(now.dist > F)// 연료를 다쓴 경우
				continue;
			
			if(now.y == gy && now.x == gx) // 목적지 도착한 경우
			{
				y = gy;// 택시의 시작 위치를 갱신
				x = gx;// 택시의 시작 위치를 갱신
				F += now.dist;// 이동거리의 2배를 연료로 충전이나 쓴연료까지하면 결국 dist플러스
				return true;
			}
			
			addQueue(now);
		}
		
		return false;
	}

	static boolean moveToPassenger() {
		// 현 위치에서 가장 가까운 승객의 위치를 찾아 택시를 그곳으로 이동하며, 연료또한 줄인다.
		clear();
		q.add(new Pos(y, x, 0));
		visit[y][x] = true;
		
		while(!q.isEmpty())
		{
			int size = q.size();// 큐에 있는 모든 데이터를 한번 훑은 후 손님 좌표를 파악함
			int minY = 1<<30;
			int minX = 1<<30;
			int dist = q.peek().dist;
			
			if(dist > F)// 연료보다 먼거리 이동이면 종료
				break;
			
			while(size-->0)
			{
				Pos now = q.poll();
				
				if(customer[now.y][now.x])// 현재 위치가 손님이 있는 위치이고
				{
					// Y좌표가 작거나, X좌표가 작은 경우 좌표 갱신
					if(minY > now.y || (minY == now.y && minX > now.x))
					{
						minY = now.y;
						minX = now.x;
					}
				}
				
				addQueue(now);
			}
			
			if(minY != 1<<30)// 손님이 있는 좌표를 구한경우
			{
				y = minY;// 택시의 현재 위치 갱신
				x = minX;// 택시의 현재 위치 갱신
				gy = destinationY[minY][minX];// 택시의 도착 목적지 갱신
				gx = destinationX[minY][minX];// 택시의 도착 목적지 갱신
				customer[minY][minX] = false;// 손님 하나 제거
				F -= dist;// 현재까지 오는데 드는 연료 제거
				return F > 0;// 연료가 0보다 큰경우 true반환
			}
			
		}
		
		return false;
	}
	static void addQueue(Pos now) {
		for(int xy[] : dxy)
		{
			int ny = now.y + xy[0];
			int nx = now.x + xy[1];
			
			if(isWall[ny][nx] || visit[ny][nx])// 벽인 경우 or 방문한 경우 스킵
				continue;
			
			visit[ny][nx] = true;
			q.add(new Pos(ny, nx, now.dist + 1));
		}
	}
	static void clear() {
		q.clear();
		for(int y=1; y<=N; y++)
			for(int x=1; x<=N; x++)
				visit[y][x] = false;
	}
	static class Pos{
		int y, x, dist;
		Pos(int y, int x, int dist){
			this.y=y;
			this.x=x;
			this.dist=dist;
		}
	}
}

 

[ 테스트 케이스 ]

6 2 2
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
6 6 5 6
4 6 4 5
답 : 2

3 1 2
0 0 0
0 0 0
0 0 0
1 1
1 3 3 1
답 : -1

5 2 20
0 1 1 1 0
0 0 0 0 0
0 1 0 1 0
0 1 0 1 1
0 1 0 0 0
4 3
2 1 5 1
2 5 3 5
답 : 13
    
5 2 10
0 0 0 0 0
0 0 0 0 0
0 0 0 1 0
0 1 0 1 0
0 0 0 0 0
5 3
3 2 1 1
4 1 1 1
답 : 10

5 2 10
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
4 2
5 1 1 1
4 4 5 4
답 : 10
    
3 9 10
0 0 0
0 0 0
0 0 0
2 2
2 2 1 1
1 1 1 2
1 2 3 3
3 3 3 2
3 2 3 1
3 1 1 3
1 3 2 1
2 1 2 3
2 3 2 2
답 : 28
    
4 2 10
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
1 2
1 1 1 4
1 4 1 1
답 : 15

6 3 2
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
1 1
1 2 2 2
2 1 3 1
4 1 4 2
답 : 2