글 읽기 - 4485 다익스트라 시간초과 도저히 모르겠습니다

dlcksdnd321 4년 전 0

priority queue를 써서 만들었는데 시간초가가 생깁니다.

해결해주시면 정말 감사하겠습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;

public class B4485 {
	static int N;
	static int[][] RUPE;
	static int[][] DIST;
	static int[] dx = { -1, 0, 1, 0 }; // 위 오른쪽 아래 왼쪽
	static int[] dy = { 0, 1, 0, -1 };

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] str;
		int problem = 1;
		while (true) {
			N = Integer.parseInt(br.readLine());
			if (N == 0)
				break;
			RUPE = new int[N][N];
			DIST = new int[N][N];
			VISITED = new boolean[N][N];
			for (int i = 0; i < N; i++) {
				str = br.readLine().split(" ");
				for (int j = 0; j < N; j++) {
					RUPE[i][j] = Integer.parseInt(str[j]);
					DIST[i][j] = Integer.MAX_VALUE;
					VISITED[i][j] = false;
				}
			}
			PriorityQueue<Dot> pq = new PriorityQueue();
			Dot start = new Dot(0, 0, RUPE[0][0]);
			DIST[0][0] = RUPE[0][0];
			pq.add(start);
			while (!pq.isEmpty()) {
				Dot dot = pq.poll();
				if( DIST[dot.x][dot.y] < dot.value) {
					continue;
				}
				for (int i = 0; i < 4; i++) {
					if (dot.x + dx[i] >= 0 && dot.x + dx[i] < N && dot.y + dy[i] < N && dot.y + dy[i] >= 0) {
						// 현재 위치에 대해 각4방향 동굴 범위 내에 판단
						if (DIST[dot.x + dx[i]][dot.y + dy[i]] > DIST[dot.x][dot.y]
								+ RUPE[dot.x + dx[i]][dot.y + dy[i]] ) {
							//다음위치에 저장된 거리가 이번에 계산된 거리보다 크다면 , 방문한적이 없고
							DIST[dot.x + dx[i]][dot.y + dy[i]] = DIST[dot.x][dot.y]
									+ RUPE[dot.x + dx[i]][dot.y + dy[i]];
							pq.add(new Dot(dot.x + dx[i], dot.y + dy[i], RUPE[dot.x + dx[i]][dot.y + dy[i]]));
						}
					}
				}
			}
			System.out.println("Problem " + problem + ": " + DIST[N-1][N-1]);
			problem++;
		}
	}

}

class Dot implements Comparable<Dot> {
	int x;
	int y;
	int value;

	public Dot(int x, int y, int value) {
		this.x = x;
		this.y = y;
		this.value = value;
	}

	@Override
	public int compareTo(Dot arg0) {
		if (this.value > arg0.value)
			return 1;
		else
			return 0;
	}
}

lemidia 4년 전 1

visited배열이 레퍼런스로 전역 선언 안되어 있어요.

클래스 Dot의 오버라이딩 함수 compareTo만 다시 고쳐주시면 될거 같습니다.

dlcksdnd321 4년 전 0

어떻게 고치면 좋을 까요 ???

lemidia 4년 전 1

우선순위 큐에 Dot이 들어가는데 value 값(오름차순) 기준으로 정렬이 되게 해야합니다.

if this < arg0 라면 -1을 반환하게 하면 되고, this > arg0 라면 1을, 같다면 0을 반환하면 됩니다.

Integer.compare(arg0, arg1)으로 비교하셔도 되고, <, >, = 비교연산자를 쓰셔도 되고, arg0 - arg1(원소끼리 값을 뺌) 이 값이 < 0 이라면 음수가 되므로

위 3개 중에 한개로 써주시면 됩니다.

아래 코드는 첫번 째 방법입니다.

@Override
    public int compareTo(Dot arg0) {
        return Integer.compare(this.value, arg0.value);
    }

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

문제

문제

출처

ICPC

4485 다익스트라 시간초과 도저히 모르겠습니다

dlcksdnd321 4년 전 0

lemidia 4년 전 1

dlcksdnd321 4년 전 0

lemidia 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말