글 읽기 - priority_queue(dijkstra)로 하면 안되는 문제인가요?

blackbbean 5년 전 0

처음에는 평범하게 bfs로 풀어서 AC를 받았습니다.

하지만, 조금 더 최적화를 해보고 싶어 Priority_queue를 사용해 보았습니다.

하지만 시간초과가...? 나네요

시간초과가 나는 이유는

prioirty queue가 힙으로 되어있는걸로 아는데 그 자료구조를 유지하기 위해서 O(logN)이 추가로 들어서 그러는건가요?

아니면

가중치가 없는 그래프에선 bfs가 더 빠른 성능을 보인다라는 원론적인 개념때문인가요?

답변 달아주시면 더욱 열심히 공부하겠습니다 :)!!

#include <iostream>
#include <queue>
#include <string.h>
using namespace std;
int dx[4] = {-1,0,1,0};
int dyy[4] = {0,1,0,-1};
int N, M, K;
int x1;
int yy1;
int x2;
int y2;
char map[1001][1001];
int visited[1001][1001];
typedef struct POS {
	int row;
	int col;
	int cnt;
	bool operator<(const POS& rhs)const {
		return cnt < rhs.cnt;
	}
};
priority_queue<POS> q;
int solve() {
	while (!q.empty()) {
		POS pd = q.top();
		if (pd.row == x2 && pd.col == y2)
			return visited[pd.row][pd.col];
		q.pop();
		for (int i = 0; i < 4; i++) {
			for (int k = 1; k <= K; k++) {
				if (pd.row + dx[i] * k<1 || pd.row + dx[i] * k>N || pd.col + dyy[i] * k<1 || pd.col + dyy[i] * k > M)
					break;
				if (map[pd.row + dx[i] * k][pd.col + dyy[i] * k] == '#')
					break;

				if (visited[pd.row + dx[i] * k][pd.col + dyy[i] * k] == -1) {
					visited[pd.row + dx[i] * k][pd.col + dyy[i] * k] = visited[pd.row][pd.col] + 1;
					q.push({ pd.row + dx[i] * k ,pd.col + dyy[i] * k ,visited[pd.row][pd.col] + 1 });
				}
				
				else if (visited[pd.row + dx[i] * k][pd.col + dyy[i] * k] > visited[pd.row][pd.col] + 1) {
					visited[pd.row + dx[i] * k][pd.col + dyy[i] * k] = visited[pd.row][pd.col] + 1;
					q.push({ pd.row + dx[i] * k ,pd.col + dyy[i] * k , visited[pd.row][pd.col]+1});
				}
				
				

			}
		}
	}
	return -1;
}
int main() {
	scanf("%d %d %d", &N, &M, &K);
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			scanf(" %1c", &map[i][j]);
		}
	}
	memset(visited, -1, sizeof(visited));
	scanf("%d %d %d %d", &x1, &yy1, &x2, &y2);
	q.push({ x1,yy1,0 });
	visited[x1][yy1] = 0;
	printf("%d",solve());
}

djm03178 5년 전 1

시간복잡도상으로는 그래서 더 느립니다.

참고로 지금 BFS로 통과하신 코드도 https://www.acmicpc.net/board/... 가 추가되고 나면 시간 초과를 받으실 것으로 보입니다.

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

문제

문제

출처

ICPC

priority_queue(dijkstra)로 하면 안되는 문제인가요?

blackbbean 5년 전 0

djm03178 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말