글 읽기 - 다익스트라 vs bfs + 우선순위큐

powerwonjun 4년 전 0

우선순위 큐 + bfs로 제출하여 맞았습니다.

제가 다른 코딩테스트에서 n과 m의 사이즈가 각 최대 500까지 가능했던 문제에서는 우선순위 큐 + bfs로 풀었을 때 시간초과가 있었습니다.

나중에 다익스트라로 고쳐 풀었을 땐 통과했었습니다.

이 문제도 단순히 n과 m이 범위가 작아서 통과했다고 생각해야 하는 건가요??

시간복잡도에 얼마나 큰 차이가 있는지 혹시 간략하게나마 설명해주실 수 있는 분 계시면 감사하겠습니다.

#include <stdio.h>
#include <algorithm>
#include <functional>
#include <memory.h>
#include <vector>
#include <queue>

using namespace std;

int N, M;
char arr[100][101];
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };
int result;
int visited[100][100];

typedef pair<int, pair<int, int>> T;
priority_queue<T, vector<T>, greater<T>> q;

void bfs(int X, int Y)
{
	q.push({ 0, {X, Y} });
	visited[X][Y] = 1;

	while (!q.empty())
	{
		int x = q.top().second.first;
		int y = q.top().second.second;
		int w = q.top().first;

		q.pop();

		if (x == M - 1 && y == N - 1)
		{
			result = w;
			return;
		}
		for (int i = 0; i < 4; i++)
		{
			int nextX = x + dx[i];
			int nextY = y + dy[i];

			if (nextX >= 0 && nextX < M && nextY >= 0 && nextY < N)
			{
				if (arr[nextX][nextY] == '0' && visited[nextX][nextY] == 0)
				{
					visited[nextX][nextY] = 1;
					q.push({ w, {nextX, nextY} });
				}
				if (arr[nextX][nextY] == '1' && visited[nextX][nextY] == 0)
				{
					visited[nextX][nextY] = 1;
					q.push({ w + 1, {nextX, nextY} });
				}
			}
		}


	}
}
int main(void)
{
	scanf("%d %d", &N, &M);
	for (int i = 0; i < M; i++)
		scanf("%s", arr[i]);

	bfs(0, 0);
	printf("%d\n", result);
}

sait2000 4년 전 2

이것도 다익스트라입니다. 다익스트라의 구현이 여러 방법이 있는데 하나는 지금 올리신 코드처럼 우선순위 큐를 사용하시면 O(E log E)인가가 나오고 매번 각 정점에 대해 루프를 돌면서 가장 가까운 안 방문한 정점을 찾는 방법이 O(V^2 + E)가 나오는데 작성하셔서 맞았다고 하시는 코드를 모르니까 더이상은 잘 모르겠네요.

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

문제

문제

출처

ICPC

다익스트라 vs bfs + 우선순위큐

powerwonjun 4년 전 0

sait2000 4년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말