글 읽기 - 우선순위큐 다익스트라 구현이 잘못되었는지 질문드립니다.

ssoo2024 4년 전 0

이 문제도 그냥 평범한 다잌스트라로 생각하고 각 칸에 도달하는 cost를 갱신해줬는데 틀렸습니다가 뜨네요 ㅠ

혹시 봐주실 수 있을까요??

게시판에 올라와있는 다른 질문인 입,출력, 좌표실수 문제는 확인했습니다.

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
using namespace std;

typedef pair<int, int> pii;
int dr[] = { -1, 1, 0 ,0 };
int dc[] = { 0, 0, -1, 1 };

int main() {
	int n, m, row, col; cin >> n >> m;
	vector<vector<int>> miro(m + 2, vector<int>(n + 2, 2)); // 미로 
	vector<vector<int>> cost(m + 2, vector<int>(n + 2, INT32_MAX)); // 각 칸에 도달하는 cost
	priority_queue<pair<int, pii>, vector<pair<int, pii>>, greater<pair<int, pii>>> q;

	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= n; j++) {
			scanf("%1d", &miro[i][j]);
		}
	}
	q.push({ cost[1][1] = 0, {1, 1} });
	while (!q.empty()) {

		for (int k = 0; k < 4; k++) { // 상,하,좌,우
			row = q.top().second.first + dr[k];
			col = q.top().second.second + dc[k];

			// miro[row][col]이 2인 경우는 범위 밖.
			if (miro[row][col] != 2 && cost[row][col] > q.top().first + miro[row][col]) {
				cost[row][col] = q.top().first + miro[row][col];
				q.push({ cost[row][col], {row, col} });
			}
			
		}
		q.pop();
	}
	printf("%d", cost[m][n]);
}

dohoon 3년 전 0

1,1에서 1,0으로 가는 경우같은 거 제외를 하신건가요..?

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

문제

문제

출처

ICPC

우선순위큐 다익스트라 구현이 잘못되었는지 질문드립니다.

ssoo2024 4년 전 0

dohoon 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말