글 읽기 - 시간초과를 줄일수 있는 방법이 있을까요?

glaems2 3년 전 0

알고리즘 공부 시작한지 별로 안되어 질문을 올립니다.

테스트 케이스는 다 돌아가는것같은데 속도가 느린것 같습니다. 최적화 할 수 있는 방법이 있을까요??

package 백준.스타트택시;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Point {
	int x, y;
	int count = 0;

	public Point(int x, int y) {
		super();
		this.x = x;
		this.y = y;
	}

	public Point(int x, int y, int count) {
		super();
		this.x = x;
		this.y = y;
		this.count = count;
	}
}

public class Main {
	static int[][] board;
	static boolean[][] visited;
	static int N, M, F; // Row, Column, Fuel
	static int[] dx = { -1, 1, 0, 0 };
	static int[] dy = { 0, 0, -1, 1 };
	static Point[] customer, destination;
	static boolean[] arrive;
	static Point taxi;
	static boolean enoughFuel = true;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		F = sc.nextInt();

		board = new int[N][N];
		visited = new boolean[N][N];

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				board[i][j] = sc.nextInt();
			}
		}
		int x = sc.nextInt() - 1;
		int y = sc.nextInt() - 1;
		taxi = new Point(x, y);

		customer = new Point[M];
		destination = new Point[M];
		arrive = new boolean[M];

		for (int i = 0; i < M; i++) {
			customer[i] = new Point(sc.nextInt() - 1, sc.nextInt() - 1);
			destination[i] = new Point(sc.nextInt() - 1, sc.nextInt() - 1);
		}

		int temp = M;
		int chargeFuel = 0;
		for (int i = 0; i < M; i++) {
			if (enoughFuel) {
				temp = findNearCustomer();  
			} else {
				System.out.println(-1);
				return ;
			}
			if (enoughFuel) {
				chargeFuel = searchDestiny(temp);
			}
			else {
				System.out.println(-1);
				return ;
			}
			F = F + chargeFuel*2;
		}
		
		System.out.println(F);
	}

	// 택시와 가장 가까운 승객을 찾는 메소드
	// 최단거리가 같을때에는 둘 중 행 번호가 더 작은 승객에게로 간다.
	private static int findNearCustomer() {
		int[] pathCnt = new int[M];

		//각 거리 값 구하고
		for (int i = 0; i < M; i++) {
			if (arrive[i])
				continue;
			visited = new boolean[N][N];
			customer[i].count = 0;
			pathCnt[i] = bfs(taxi, customer[i]);
		}

		int min = Integer.MAX_VALUE;
		int index = 0;
		
		//최소값을 구해준다
		for (int i = 0; i < M; i++) {
			if (arrive[i])
				continue;
			if (min > pathCnt[i]) {
				min = pathCnt[i];
				index = i;
			} else if (min == pathCnt[i]) {
				index = customer[i].x < customer[index].x ? i : index;
			}
		}
		
		if (F - min <= 0) {
			enoughFuel = false;
		} else {
			taxi = customer[index];
			arrive[index] = true;
			F -= min;
		}
		return index;
	}

	// 도착지까지 가장 가까운 경로 찾는 메소드
	// 기름이 채워지는 것은 승객과 목적지 사이의 연료 소모 값 x 2배
	private static int searchDestiny(int a) {
		int pathCnt = 0;

		visited = new boolean[N][N];
		pathCnt = bfs(taxi, destination[a]);
		taxi = destination[a];
		if (F - pathCnt <= 0) {
			enoughFuel = false;
		} else {
			F -= pathCnt;
		}
		
		return pathCnt;
	}

	// 승객 찾아가기 && 목적지 찾아가기
	private static int bfs(Point start, Point end) {
		Queue<Point> queue = new LinkedList<Point>();
		queue.add(start);
		visited[start.x][start.y] = true;

		while (!queue.isEmpty()) {
			Point temp = queue.poll();
			if (temp.x == end.x && temp.y == end.y) {
				return temp.count;
			}

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

				if (nx >= 0 && ny >= 0 && nx < N && ny < N) {
					if (!visited[nx][ny] && board[nx][ny] == 0) {
						queue.add(new Point(nx, ny, temp.count + 1));
						visited[nx][ny] = true;
					}
				}
			}
		}

		return Integer.MAX_VALUE;
	}
}

danimartinwife 3년 전 1

우선 승객 찾으실 때 클래스 쪽(c계열에서는 구조체) 보니까 연산자 오버로딩을 활용하셔서 정렬 라이브러리를 써보세요. 그리고 저같은 경우는 거리를 전처리로 구했습니다. 우선 소스 전체를 올려드리긴 좀 그렇고, 구조체 부분만 공유해드리겠습니다.

순서 부분만 다시 한번 생각해보시면 통과되실거에요. (BFS 메소드는 그대로 두심 될거같아요) 그런데 소스 정말 가독성 좋으신데, 개발 경력이 따로 있으신가봐요! 현재 취준중인데 알고리즘이야 답만 나오면 되지만, 현업 가면 소스 가독성도 중요하다고 들어서요.

struct Driver { //운전자의 현재 정보를 나타내는 구조체
	pii p; int gas;
	Driver(pii p, int gas) {
		this->p = p;
		this->gas = gas;
	}
	Driver() {}
};

struct Info {
	int idx;  pii st, en; int gas; int dist;
	Info(int idx, pii st, pii en, int gas) {
		this->idx = idx; //손님 번호
		this->st = st; //시작점
		this->en = en; //도착점
		this->gas = gas; //출발점부터 도착점까지 최단 거리
		this->dist = dist; //현재 운전사랑 거리
	}
	Info () {}
};

bool cmp (const Info &a, const Info &b) {
	if (a.dist == b.dist) {
		if (a.st.first == b.st.first) {
			return a.st.second > b.st.second;
		}
		return a.st.first > b.st.first;
	}
	return a.dist > b.dist;
}

/*
전 c++ 클래스가 익숙하지 않아서 따로 뺐는데 자바일 경우 정렬 기준을 클래스 내부에 넣으시면 됩니다.
*/

glaems2 3년 전 1

친절한 설명 감사합니다! 운전사 구조체와 운전자와 승객 간 정보를 만들어서 사용하셨네요. 좋은 조언 얻고갑니다 :)
부족한 알고리즘 좋게 봐주셔서 감사합니다. 저도 아직 취준중이에요 ㅎㅎ 외국에서 php로 짧게 인턴하다가 들어왔습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과를 줄일수 있는 방법이 있을까요?

glaems2 3년 전 0

danimartinwife 3년 전 1

glaems2 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말