[JAVA] 백준 스타트택시

dfs방식으로 문제를 풀었는데 시간초과가 됐다.

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

class Main {
    static boolean[][] visit;
    static int[][] grid;
    static int N, M, fuel;
    static int taxiX, taxiY;
    static Guest[] guests;
    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());
        fuel = Integer.parseInt(st.nextToken());
        visit = new boolean[N][N];
        grid = new int[N][N];
        guests = new Guest[M];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                grid[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        st = new StringTokenizer(br.readLine());
        taxiY = Integer.parseInt(st.nextToken())-1;
        taxiX = Integer.parseInt(st.nextToken())-1;
        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            int a=Integer.parseInt(st.nextToken())-1;
            int b=Integer.parseInt(st.nextToken())-1;
            int c=Integer.parseInt(st.nextToken())-1;
            int d=Integer.parseInt(st.nextToken())-1;

            guests[i] = new Guest(a,b,c,d);
        }

        for(int i=0; i<M; i++){
            int reFill = selectGuest();
            if(reFill<0){//앵꼬
                System.out.println(-1);
                return;
            }
            fuel+= reFill;
            //System.out.println(i+"번째 남은연료:" + fuel);
        }
        System.out.println(fuel);
    }
    static int selectGuest(){
        int minDistFromTaxi = Integer.MAX_VALUE;
        int guestNum=0;
        for(int i=0; i<M; i++){
            minDist = Integer.MAX_VALUE;
            Guest g = guests[i];
            if(g.visit){//방문한곳
                continue;
            }
            shortestPath(taxiX, taxiY, g.sx, g.sy, 0);//출발점구하고
            //System.out.println(count);
            count=0;
            if(minDistFromTaxi>minDist){//------------------<거리가 서로 다른경우>
                //System.out.println("-->" + minDist+"목표위치"+ g.sx+","+ g.sy);
                guestNum=i;//몇번째 게스트인지.저장
                minDistFromTaxi=minDist;
            }else if(minDistFromTaxi== minDist){//---------<거리가 서로 같은경우 비교>
                //System.out.println(minDistFromTaxi + " vs "  + minDist);
                if(guests[guestNum].sy > g.sy){//1. 행값 작은걸로
                    guestNum=i;
                }else if(guests[guestNum].sy < g.sy) guestNum=guestNum;//그대로
                else{//2. 열값 작은걸로
                    if(guests[guestNum].sx > g.sx){//1. 행값 작은걸로
                        guestNum=i;
                    }else if(guests[guestNum].sx < g.sx) guestNum=guestNum;
                }
            }
        }
        //ystem.out.println("방문한곳 : " + guestNum);
        guests[guestNum].visit=true;//방문했으니 바꿔주고
        //택시
        fuel-=minDistFromTaxi;//데릴러가기
        if(fuel<0) return -9999999;//만약 데릴러가다 앵꼬
        int consumedFuel = gotoGoal(guestNum);
        fuel-= consumedFuel;
        if(fuel<0) return -9999999;//만약 데려다주다 앵꼬

        return consumedFuel*2;
    }

    static int gotoGoal(int gNum){//데려다주기
        Guest g = guests[gNum];
        minDist=Integer.MAX_VALUE;//초기화
        shortestPath(g.sx, g.sy, g.dx, g.dy, 0);

        taxiX= g.dx;
        taxiY= g.dy;
        return minDist;
    }

    static int[] dirx= {0,1,0,-1};
    static int[] diry= {1,0,-1,0};
    static int minDist=Integer.MAX_VALUE;
    static int count=0;
    static void shortestPath(int sx, int sy, int dx, int dy, int depth) {//start x y , destination x y
        if(depth == minDist) return;//시간단축
        if(sx==dx && sy==dy){//목적지 도착하면 갱신
            count++;
            minDist = Math.min(minDist,depth);
            return;
        }

        for(int i=0; i<4; i++){
            int ssx=sx+dirx[i];
            int ssy=sy+diry[i];
            if(ssx>=0 && ssx<N && ssy>=0 && ssy<N && grid[ssy][ssx] != 1 && !visit[ssy][ssx]) {//범위내 & 벽x
                visit[ssy][ssx] = true;
                shortestPath(ssx, ssy, dx, dy, depth + 1);
                visit[ssy][ssx] = false;
            }
        }
        return;
    }
    static class Guest{
        int sx, sy, dx, dy;
        boolean visit = false;
        Guest(int sy, int sx, int dy, int dx){
            this.sx= sx;
            this.sy=sy;
            this.dx=dx;
            this.dy=dy;
        }
    }

}

bfs방식으로 푸는것이 맞다고 하니, 아래의 코드는 bfs코드이다.

import java.io.*;
import java.util.*;

class Node implements Comparable<Node> {
	int x, y, dist;

	public Node(int x, int y, int dist) {
		this.x = x;
		this.y = y;
		this.dist = dist;
	}

	@Override
	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;
			}
		}
	}
}

class Path {
	int start_x, start_y, end_x, end_y;

	public Path(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;
	}
}

public class Main {
	static int N, M, fuel;
	static int[][] map;
	static boolean[][] visited;
	static int joon_x, joon_y;

	static int[] dx = { -1, 0, 1, 0 };
	static int[] dy = { 0, 1, 0, -1 };

	static ArrayList<Node> startList = new ArrayList<>();
	static ArrayList<Path> pathList = new ArrayList<>();

	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());
		fuel = Integer.parseInt(st.nextToken());
		map = new int[N + 1][N + 1];
		visited = new boolean[N + 1][N + 1];

		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 1; j <= N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if (map[i][j] == 1) {
					map[i][j] = -1;
				}
			}
		}

		st = new StringTokenizer(br.readLine());
		joon_x = Integer.parseInt(st.nextToken());
		joon_y = Integer.parseInt(st.nextToken());

		boolean flag = false;
		for (int i = 1; i <= M; i++) {
			st = new StringTokenizer(br.readLine());
			int start_x = Integer.parseInt(st.nextToken());
			int start_y = Integer.parseInt(st.nextToken());
			int end_x = Integer.parseInt(st.nextToken());
			int end_y = Integer.parseInt(st.nextToken());
			pathList.add(new Path(start_x, start_y, end_x, end_y));
			map[start_x][start_y] = i;
		}

		while (true) {
			if (pathList.size() == 0) { // 모두 데려다줬을 경우
				System.out.println(fuel);
				return;
			}

			startList.clear();
			visited = new boolean[N + 1][N + 1];

			getStart(joon_x, joon_y); // 출발지 선정

			if (startList.size() == 0) { // 벽에 막힌 경우
				System.out.println(-1);
				return;
			}

			Node start = startList.get(0);
			map[start.x][start.y] = 0;
			fuel -= start.dist;

			if (fuel < 0) {	// 연료 떨어진 경우
				System.out.println(-1);
				return;
			}

			visited = new boolean[N + 1][N + 1];

			int dist = 0;
			for (int i = 0; i < pathList.size(); i++) { // 도착지 선정
				Path path = pathList.get(i);

				if (path.start_x == start.x && path.start_y == start.y) {
					dist = getDist(path.start_x, path.start_y, path.end_x, path.end_y);

					if (dist == -1) { // 벽에 막힌 경우
						System.out.println(-1);
						return;
					}
					joon_x = path.end_x;
					joon_y = path.end_y;
					pathList.remove(path);
					break;
				}
			}

			fuel -= dist;

			if (fuel < 0) {	// 연료 떨어진 경우
				System.out.println(-1);
				return;
			}

			fuel += dist * 2;
		}

	}

	public static void getStart(int x, int y) {
		PriorityQueue<Node> q = new PriorityQueue<>();
		q.add(new Node(x, y, 0));

		while (!q.isEmpty()) {
			Node cur = q.poll();
			if (map[cur.x][cur.y] >= 1) {
				startList.add(new Node(cur.x, cur.y, cur.dist));
				break;
			}

			for (int i = 0; i < 4; i++) {
				int nx = cur.x + dx[i];
				int ny = cur.y + dy[i];
				if (nx > 0 && nx <= N && ny > 0 && ny <= N) {
					if (map[nx][ny] != -1 && !visited[nx][ny]) {
						visited[nx][ny] = true;
						q.add(new Node(nx, ny, cur.dist + 1));
					}
				}
			}
		}
	}

	public static int getDist(int start_x, int start_y, int end_x, int end_y) {
		Queue<Node> q = new LinkedList<>();
		q.add(new Node(start_x, start_y, 0));

		while (!q.isEmpty()) {
			Node cur = q.poll();
			if (cur.x == end_x && cur.y == end_y) {
				return cur.dist;
			}

			for (int i = 0; i < 4; i++) {
				int nx = cur.x + dx[i];
				int ny = cur.y + dy[i];
				if (nx > 0 && nx <= N && ny > 0 && ny <= N) {
					if (map[nx][ny] != -1 && !visited[nx][ny]) {
						visited[nx][ny] = true;
						q.add(new Node(nx, ny, cur.dist + 1));
					}
				}
			}
		}
		return -1;
	}
}