글 읽기 - 알고스팟 문제 질문있습니다.

yeop9657 7년 전 0

안녕하세요.

알고스팟 문제를 풀다가 막히는 부분이 풀리지 않아서 질문을 드립니다.

우선 다익스트라를 통해서 최소 값을 선택해가면서 경로를 지정하면서 진행하고 있습니다.

그런데 문제는 경로를 최솟값을 선택하다보니 어느순간 1과 0이 있으면 1로 가야하는 순간에 0으로 가버려서 더 높은 값이 나와버립니다.

이런 경우는 어떠한 예외 처리를 해주어야 하나요?

#include <queue>
#include <cstdio>
#include <iostream>
using namespace std;

/* Define */
#define SIZE 101
#define INF 100000000L

/* Array */
int mArray[SIZE][SIZE];
bool mVisit[SIZE][SIZE];

/* Function Declare */
int minDijkstra(const int mStart, const int mEnd);

int main(void)
{
    /* Integer */
    int mRow = 0, mCol = 0;
    cin >> mRow >> mCol;
    
    /* Init Array */
    for (int ii = 0; ii <= mCol; ii++)
    { for (int jj = 0; jj <= mRow; jj++) { mArray[ii][jj] = INF; mVisit[ii][jj] = false; } }
    
    /* Input */
    for (int ii = 0; ii < mCol; ii++)
    {
        getchar();
        for (int jj = 0; jj < mRow; jj++)
        { mArray[ii][jj] = getchar() - '0'; }
    }
    
    /* Output */
    cout << minDijkstra(mCol - 1, mRow - 1) << endl;
        
    return 0;
}

/* Function Define */
int minDijkstra(const int mStart, const int mEnd)
{
    /* Integer */
    int mSubX = 0, mSubY = 0;
    mVisit[mSubX][mSubY] = true;
    
    /* Queue */
    queue<pair<int, int> > mPath;
    mPath.push(make_pair(mSubX, mSubY));
    
    while (!mVisit[mStart][mEnd])
    {
        /* Integer */
        int mMin = INF;
        
        /* Pair<int, int> */
        pair<int, int> mLocation;
        pair<int, int> mPosition[4] = {make_pair(1, 0), make_pair(0, 1), make_pair(-1, 0), make_pair(0, -1)};
        
        mSubX = mPath.front().first; mSubY = mPath.front().second; mPath.pop();
        for (int jj = 0; jj < 4; jj++)
        {
            int mLowX = mSubX + mPosition[jj].first, mColY = mSubY + mPosition[jj].second;
            if ((mLowX >= 0 && mColY >= 0) && (mLowX <= mStart && mColY <= mEnd))
            {
                /* Visit Check */
                if (mVisit[mLowX][mColY]) { continue; }
                
                mArray[mLowX][mColY] = mArray[mSubX][mSubY] + mArray[mLowX][mColY];
                if (mMin > mArray[mLowX][mColY]) { mMin = mArray[mLowX][mColY]; mLocation = make_pair(mLowX, mColY); }
            }
        }
    
        mPath.push(mLocation);
        mVisit[mLocation.first][mLocation.second] = true;
        cout << mLocation.first << " " << mLocation.second << endl;
    }
    
    return mArray[mStart][mEnd];
}

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

문제

문제

출처

ICPC

알고스팟 문제 질문있습니다.

yeop9657 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말