[BOJ] 19238 스타트 택시 - Java

✨ 구현 & BFS(최단거리)

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

19238번: 스타트 택시

---

📍 고려해야할 점

• 택시의 위치에서부터 승객까지의 최단거리를 구한다. 👉 시간초과 주의 !
• 최단거리가 동일한 승객들이 존재할 경우 그 중 행 번호가 가장 작은 승객을, 그런 승객도 여러 명이라면 열 번호가 가장 작은 승객에게 이동한다. 👉 PriorityQueue 활용
• 벽에 의해 승객에게 가지 못하거나 목적지에 가지 못하는 상황 또한 발생한다. 👉 목적지로 이동할 때 고려하지 않아 틀렸었다.. 
• 택시가 승객의 목적지로 이동하였을 때 그 위치는 다른 승객의 시작점일 수 있다. 👉 이럴 경우 택시는 굳이 안 움직여도 된다 ! 이 조건 또한 고려하지 못해서 틀렸었다..
• 연료가 이동 도중에 떨어지면 -1을 출력하고 프로그램을 종료한다.
• 이동하지 못하는 상황을 flag을 통해 중간중간 확인해야한다. 

 

🕹️ 풀이방법 

처음 풀 때 무난하다 싶었는데 시간초과가 발생했다. .

각각의 승객의 거리를 모두 구한 후 PriorityQueue를 사용해 조건에 해당하는 운전자를 선택하는 방식으로 작성했는데 이 풀이법은 BFS를 승객의 수만큼 계속 돌기 때문에 시간초과가 발생한 것이다. 

 

단순하게 생각하면 된다. 

1. board에 승객의 번호(1~M)을 기입하고, 벽은 -1로 대체한다. 
2. 현재 택시의 위치로부터 BFS를 하며 이동한 위치가 0보다 크다면 즉, 승객이 위치해있다면 PriorityQueue에 해당하는 위치와 거리를 넣는다. 
3. 탐색을 마치고 PriorityQueue를 poll하면 조건에 적합한 승객이 나온다.
4. 그 승객에게 이동하고, 승객의 목적지로 이동한다. 

---

🔹 findPassenger() : 최단거리에 있는 승객 찾기  

// #1. 최단거리에 있는 승객 찾기 --> 승객의 번호 반환
static int findPassenger() {

	// 만약 현재 택시 위치가 승객의 시작점이라면 그 승객의 번호를 반환한다. (이동 X)
    if(board[tx][ty]>0) return board[tx][ty];
    
    PriorityQueue<Info> pq = new PriorityQueue<>();
    Queue<Info> q = new LinkedList<>();
    boolean[][] visit = new boolean[N][N];
    q.add(new Info(tx, ty, 0));

    int dist=0;
    while(!q.isEmpty()) {
        Info now = q.poll();

        for(int i=0; i<4; i++) {
            int nx = now.x+dx[i];
            int ny = now.y +dy[i];
		
            if(inRange(nx, ny) && !visit[nx][ny] && board[nx][ny]!=-1) {
                visit[nx][ny]=true;
                dist = now.d+1;
				
                // 해당하는 위치에 승객이 있다면 승객의 정보를 우선순위 큐에 넣는다.
                if(board[nx][ny]>0) pq.add(new Info(nx, ny, dist));

                q.add(new Info(nx, ny, dist));
            }

        }
    }

	// 승객에게 갈 수 없을 경우 우선순위 큐는 비어있다. ➔ flag로 나타내서 -1을 출력하도록 한다.
    if(pq.isEmpty()) {
        flag= true;
        return 0;
    }

    Info p = pq.poll();
    // 승객에게 이동하는데 연료가 부족하면 flag을 표시하고 -1을 출력하도록 한다. 
    if(F<=p.d) flag=true;
    
    // 승객에게 이동할 수 있다면 연료를 소모한다.
    else F-=p.d;
    
    // 승객의 번호를 반환한다.
    return board[p.x][p.y];
}

 

🔹 moveToDest(int idx) : 승객의 목적지로 이동 

// #2. 승객의 목적지로 이동
static int moveToDest(int idx) {

	// idx = 승객의 번호 
    Info dest = destination[idx];
    Queue<Info> q = new LinkedList<>();
    boolean[][] visit = new boolean[N][N];
    visit[tx][ty]= true; 
    int dist=0;
    q.add(new Info(tx, ty, 0));
    
    while(!q.isEmpty()) {
        Info now = q.poll();
        // 승객의 목적지에 도착했다면 return 
        if(now.x==dest.x && now.y==dest.y) {
        	// 만약 연료가 부족하다면 -1을 반환
            if(F<now.d) return -1;
            
            // 이동할 수 있다면 연료를 소모하고 충전한다. 
            else {
                F-=now.d;
                F+=(now.d*2);
                return now.d;
            }
        }

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

            if(inRange(nx, ny)&&!visit[nx][ny] && board[nx][ny]!=-1) {
                visit[nx][ny] = true;
                dist = now.d+1;
                q.add(new Info(nx, ny, dist));
            }
        }
    }
    return -1;
}

 

🔹 simulate() : 모든 함수 통합 

static void simulate() {

	// 최단거리에 있는 승객을 찾고 그 승객의 번호를 반환한다.
    int idx = findPassenger();
    
    // 택시 ~ 승객 거리가 연료보다 크거나 같다면 이동 X or 벽으로 인해 승객에게 갈 수 없다면 끝 
    if(flag) {
        resultFlag=true;
        return; 
    }
    
    // 택시를 운전자에게 이동시키기 
    Info p = start[idx];
    moveTaxi(p.x, p.y);
    
    // 승객의 목적지로 이동했을 때의 거리를 반환한다.
    int dist = moveToDest(idx);
    
    // 택시 ~ 목적지 거리가 연료보다 크면(= moveToDest()의 반환값이 -1이라면) 이동 불가
    if(dist==-1) {
        resultFlag=true;
        return;
    }
    
    // 택시를 목적지로 이동시키기 
    Info pe = destination[idx];
    moveTaxi(pe.x, pe.y);
    
    // 승객을 이동시켰으므로 승객 제거
    board[p.x][p.y] = 0;
}

 

👩‍💻 전체 코드 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ_19238_스타트택시 {
	static int N, M, F;
	static int[][] board;
	static int tx, ty; // 택시의 위치
	static Info[] start;
	static Info[] destination;
	static boolean flag;
	static boolean resultFlag;
	static int[] dx = {0, 0, -1, 1};
	static int[] dy = {1, -1, 0, 0};
	
	
	static class Info implements Comparable<Info>{
		int x, y, d;
		
		public Info(int x, int y, int d) {
			this.x=x;
			this.y=y;
			this.d=d;
		}

		@Override
		public int compareTo(Info o) {
			if(d==o.d) {
				if(x==o.x) return y-o.y;
				else return x-o.x;
			}else return d-o.d;
		}
	}
	
	static void simulate() {
		int idx = findPassenger();
		// 택시 ~ 승객 거리가 연료보다 크거나 같다면 이동 X or 벽으로 인해 승객에게 갈 수 없다면 끝 
		if(flag) {
			resultFlag=true;
			return; 
		}
		Info p = start[idx];
		moveTaxi(p.x, p.y);
		int dist = moveToDest(idx);
		// 택시 ~ 목적지 거리가 연료보다 크면 이동 불가
		if(dist==-1) {
			resultFlag=true;
			return;
		}
		Info pe = destination[idx];
		moveTaxi(pe.x, pe.y);
		board[p.x][p.y] = 0;
	}
	
	// #1. 최단거리에 있는 승객 찾기 --> 승객의 번호 반환
	static int findPassenger() {
		if(board[tx][ty]>0) return board[tx][ty];
		PriorityQueue<Info> pq = new PriorityQueue<>();
		Queue<Info> q = new LinkedList<>();
		boolean[][] visit = new boolean[N][N];
		q.add(new Info(tx, ty, 0));

		int dist=0;
		while(!q.isEmpty()) {
			Info now = q.poll();
			
			for(int i=0; i<4; i++) {
				int nx = now.x+dx[i];
				int ny = now.y +dy[i];
				
				if(inRange(nx, ny) && !visit[nx][ny] && board[nx][ny]!=-1) {
					visit[nx][ny]=true;
					dist = now.d+1;
					
					if(board[nx][ny]>0) pq.add(new Info(nx, ny, dist));
					
					q.add(new Info(nx, ny, dist));
				}
			}
		}
		
		if(pq.isEmpty()) {
			flag= true;
			return 0;
		}
		
		Info p = pq.poll();
		if(F<=p.d) flag=true;
		else F-=p.d;
		return board[p.x][p.y];
	}
	
	// #2. 택시가 특정 위치 (승객 위치 또는 목적지)로 이동	
	static void moveTaxi(int x, int y) {
		tx = x;
		ty = y;
	}
	
	// #3. 승객의 목적지로 이동
	static int moveToDest(int idx) {
		Info dest = destination[idx];
		Queue<Info> q = new LinkedList<>();
		boolean[][] visit = new boolean[N][N];
		visit[tx][ty]= true; 
		int dist=0;
		q.add(new Info(tx, ty, 0));
		while(!q.isEmpty()) {
			Info now = q.poll();
			if(now.x==dest.x && now.y==dest.y) {
				if(F<now.d) return -1;
				else {
					F-=now.d;
					F+=(now.d*2);
					return now.d;
				}
			}
			
			for(int i=0; i<4; i++) {
				int nx = now.x+dx[i];
				int ny = now.y+dy[i];
			
				if(inRange(nx, ny)&&!visit[nx][ny] && board[nx][ny]!=-1) {
					visit[nx][ny] = true;
					dist = now.d+1;
					q.add(new Info(nx, ny, dist));
				}
			}
		}
		return -1;
	}
	
	
	static boolean inRange(int x, int y) {
		if(x>=0 && x<N && y>=0 && y<N) return true;
		return false;
	}
	
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		F = Integer.parseInt(st.nextToken());
		
		board = new int[N][N];
		start = new Info[M+1];
		destination = new Info[M+1];
		
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<N; j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
				if(board[i][j]==1) board[i][j]=-1;
			}
		}
	
		st = new StringTokenizer(br.readLine());
		
		tx = Integer.parseInt(st.nextToken())-1;
		ty = Integer.parseInt(st.nextToken())-1;
		
		
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			
			int sx = Integer.parseInt(st.nextToken())-1;
			int sy = Integer.parseInt(st.nextToken())-1;
			int ex = Integer.parseInt(st.nextToken())-1;
			int ey = Integer.parseInt(st.nextToken())-1;
			
			board[sx][sy] = i+1;
			
			start[i+1] = new Info(sx, sy, 0);
			destination[i+1]=new Info(ex, ey, 0);
		}
		
		for(int i=0; i<M; i++) {
			simulate();
			if(resultFlag) break;
		}
		
		if(resultFlag) bw.write(-1 + " ");
		else bw.write(F + " ");
		bw.flush();
		bw.close();
	}
}