글 읽기 - BFS + 우선순위큐

skesswswkk 1년 전 0

BFS + 우선순위큐 로 풀었는데 4%에서 틀렸습니다 가 뜹니다.

구글링해서 정답코드와 비교해봤는데, 어느 부분 차이가 있는지 모르겠습니다.

조언 부탁드립니다.

//틀렸습니다 코드
#include <iostream>
#include <string> //find
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
#include <set>
#include <vector>
#include <queue>
#include <climits>
#include <map>
using namespace std;
const int M = 1000 + 500;

int arr[M][M];
int visited[M][M];
typedef struct{
    int diff;
    int r;
    int c;
}st;

int dr[4] = {-1, 1, 0, 0};
int dc[4] = {0, 0, -1, 1};

struct cmp{
    bool operator()(st & a, st & b){
        if(a.diff != b.diff) return a.diff > b.diff;
        else  if(a.r != b.r) return a.r > b.r;
        else return a.c > b.c;
    }
};

int main(){
    int n;
    cin >> n;
    
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= n; ++j){
            cin >> arr[i][j];
        }
    }
    
    if(n == 1) {
        cout << 0 << "\n";
        exit(0);
    }
    
    priority_queue<st, vector<st>, cmp> q;
    q.push({abs(arr[1][1] - arr[1][2]), 1, 2});
    q.push({abs(arr[1][1] - arr[2][1]), 2, 1});
    visited[1][1] = 1;
    visited[1][2] = 1;
    visited[2][1] = 1;
    int ans = 0;
    while(!q.empty()){
        int diff2 = q.top().diff;
        int rr = q.top().r;
        int cc = q.top().c;
//        cout << rr << ", " << cc << " : " << diff2 << endl;
//        visited[rr][cc] = 1;
        q.pop();
        
        ans = max(ans, diff2);
        
        //종료조건
        if(rr == n && cc == n){
            cout << ans << endl;
            exit(0);
        }
        
        for(int i = 0; i < 4; ++i){
            int nr = rr + dr[i];
            int nc = cc + dc[i];
            if(1 <= nr && nr <= n && 1 <= nc && nc <= n){
                if(visited[nr][nc] == 0){
                    visited[nr][nc] = 1;
                    q.push({ abs(arr[rr][cc] - arr[nr][nc]), nr, nc});
                }
            }
        }
    }
}


//구글링 맞았습니다 코드
#include <iostream>
#include <string> //find
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
#include <set>
#include <vector>
#include <queue>
#include <climits>
#include <map>
using namespace std;
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
 
int arr[1001][1001];
int dist[1001][1001];
int n;
int INF, ans=0;
priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;
 
void dijkstra() {
    while (!pq.empty()) {
        int curcost = pq.top().first;
        int curx = pq.top().second.first;
        int cury = pq.top().second.second;
        pq.pop();
 
        if (dist[curx][cury] != INF) continue;
        dist[curx][cury] = curcost;
 
        ans = max(ans, curcost);
        if (curx == n - 1 && cury == n - 1) break;
        for (int i = 0; i < 4; i++) {
            int nextx = curx + dx[i];
            int nexty = cury + dy[i];
 
            if (nextx < 0 || nextx >= n || nexty < 0 || nexty >= n) continue;
            if (dist[nextx][nexty] == INF ) {
                pq.push(make_pair(abs(arr[nextx][nexty] - arr[curx][cury]),make_pair(nextx, nexty)));
                
            }
 
        }
    
    }
 
}
int main(void) {
    ios::ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> arr[i][j];
        }
    }
    if (n == 1) {
        cout << 0 << '\n';
        return 0;
    }
    pq.push(make_pair(abs(arr[0][0] - arr[0][1]), make_pair(0, 1)));
    pq.push(make_pair(abs(arr[0][0] - arr[1][0]), make_pair(1, 0)));
 
    memset(dist, 127, sizeof(dist));
 
    INF = dist[0][0];
 
    dist[0][0] = 0;
 
    dijkstra();
 
    cout << ans << '\n';
}

zenith82114 1년 전 2

다익스트라에서 방문 체크는 큐에 넣을 때가 아니라 꺼낼 때 합니다.

큐에서 꺼내지기 전까지는 최단 경로를 찾았다고 장담할 수 없기 때문입니다.

큐에서 실제로 꺼내지 않았는데도 방문 체크를 했기 때문에

더 좋은 경로를 뒤늦게 찾아도 방문 체크 때문에 무시됩니다.

*** 반례 ***

입력
3
20 15 20
5 10 20
2 1 0

정답
5
출력
20

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

문제

문제

출처

ICPC

BFS + 우선순위큐

skesswswkk 1년 전 0

zenith82114 1년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말