[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;
‌}
}