글 읽기 - 논리적으로 문제가 없어보입니다...

gidskql6671 3년 전 0

우선순위 큐를 이용해 min값과 max값을 계속 들고가면서 차이가 최소가 되는 루트를 찾도록 하였습니다. 제가 생각하기에 논리적으로는 틀린 것이 없어보입니다... 하다못해 시간초과나 메모리초과가 발생한 것이라면 마음이 편할건데, 어디서 틀린 것인지 도저히 모르겠습니다.

질문게시판에 있던 반례는 모두 맞는 답이 나오고, 제가 임의로 입력한 테스트케이스들도 모두 정답처리됩니다... 혹시 어디서 틀린 것인지, 혹은 반례가 있다면 알려주신다면 감사하겠습니다.

#include <bits/stdc++.h>
#define INF 987654321
using namespace std;
typedef long long ll;


int n;
int arr[105][105];
int visited[105][105];
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

// (x, y)가 배열의 내부에 있는지 여부를 체크하는 함수. 
bool check(int x, int y){
    return (0 <= x && x < n && 0 <= y && y < n);
}

int bfs(int sx, int sy){
    // dif, x, y, min, max
    priority_queue<tuple<int, int, int, int, int>, vector<tuple<int, int, int, int, int>>, greater<tuple<int, int, int, int, int>>> pq;
    // 시작점과 도착점의 값 차이, 시작지점x, 시작지점y, 시작점과 도착점의 값 중 최소값, 시작점과 도착점의 값 중 최대값
    pq.emplace(max(arr[0][0], arr[n-1][n-1]) - min(arr[0][0], arr[n-1][n-1]), sx, sy, min(arr[0][0], arr[n-1][n-1]), max(arr[0][0], arr[n-1][n-1]));
    
    // 방문하지않은 곳은 INF로 초기화.
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            visited[i][j] = INF;
    visited[0][0] = 0;
    
    while(!pq.empty()){
        int dif, x, y, Min, Max;
        tie(dif, x, y, Min, Max) = pq.top();
        pq.pop();
        
        // 도착했으면 dif 반환. 우선순위 큐라서 가장 작은 값임이 보장됨.
        if (x == n - 1 && y == n - 1)
            return dif;
        
        // 상하좌우 이동
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i], ny = y + dy[i];
            
            // (nx, ny)가 배열 범위 이내라면
            if (check(nx, ny)){
                // arr[ny][nx]의 값을 통해 min과 max, dif값을 최신화 해줌.
                int nMin = min(Min, arr[ny][nx]);
                int nMax = max(Max, arr[ny][nx]);
                int ndif = nMax - nMin;
                
                // 만약 다음 방문할 곳을 방문한 적이 없거나, 방문했더라도 ndif값보다 클경우 우선순위 큐에 추가.
                if (visited[ny][nx] > ndif){
                    visited[ny][nx] = ndif;
                    pq.emplace(ndif, nx, ny, nMin, nMax);
                }
            }
        }
    }
    
    // 의미없는 return. 반복문 내에서 끝나는게 보장됨.
    return 0;
}

int main(){
    ios::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];
    
    cout << bfs(0, 0) << endl;
    
    return 0;
}

skeep194 3년 전 1

3
5 0 100
10 5 0
100 0 5

답은 95인데 이 코드는 100을 출력하네요.

과연 5, 10으로 와서 dif=5인 경우와 0, 5로 와서 dif=5인 경우가 같을까요?

그렇지 않아서 생기는 문제입니다.

skeep194 3년 전 1

답은 95인데 이 코드는 100 -> 답은 5인데 이 코드는 10입니다..

gidskql6671 3년 전 0

감사합니다 😀

k550706 1년 전 0

저 예제 코드의 답은 5 아닌가요??

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

문제

문제

출처

ICPC

논리적으로 문제가 없어보입니다...

gidskql6671 3년 전 0

skeep194 3년 전 1

skeep194 3년 전 1

gidskql6671 3년 전 0

k550706 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말