글 읽기 - 정답은 맞췄으나 두 코드가 어떻게 다른지 자세하게 설명 주실분?

khndhkx123 4년 전 0

우선은 제가 처음에 짯던 단순BFS 입니다.

다익스트라 유형임을 알고도 사실 BFS로 항상 최소값만 저장해서 걸어가면 결국엔 똑같이 답이 되지 않을까 해서 정석의 다익스트라 말고 비슷하지만 BFS로만 짯다고 할수있는 방법으로 해봤습니다.

설명 :

재방문을 허용하지만 check 배열에 의해 재방문일 경우 값만 더 작은값으로 변경이 허용되고, 큐 안에 push 는 하지 않는 것으로 시간초과를 면하고 좋은 방법이라 생각했습니다.

checkmap 은 input 을 그대로 복사한 것입니다. map 에다가 직접 값을 수정하기 때문이죠.

check 배열은 bool 타입 방문여부 체크입니다.

void BFS(int y, int x)
{
    int newy, newx;
    vector<vector<int> >checkmap = map;
    queue<pair<int,int> >Q;
    pair<int,int>block;
    Q.push(make_pair(y,x)); check[y][x] = true;

    while(!Q.empty())
    {
        block = Q.front(); Q.pop();

        for(int i=0; i<4; ++i)
        {
            newy = block.first + dy[i];
            newx = block.second + dx[i];

            if(newy < 0 || newx < 0 || newy >= M || newx >= N) continue;

            if(!check[newy][newx])
            {
                if(checkmap[newy][newx] == 1) map[newy][newx] = map[block.first][block.second]+1;
                else map[newy][newx] = map[block.first][block.second];
                Q.push(make_pair(newy,newx)); check[newy][newx] = true;
            }
            else
            {
                if(checkmap[newy][newx] == 1 && map[block.first][block.second]+1 < map[newy][newx]) map[newy][newx] = map[block.first][block.second]+1;
                else if(checkmap[newy][newx] == 0 && map[block.first][block.second] < map[newy][newx]) map[newy][newx] = map[block.first][block.second];
            }
        }
    }
}

khndhkx123 4년 전 0

그리고 이것이 정석인 다익스트라로 짠 것입니다.

이론적인 부분은 이해했으나, 걸어가는 과정에서..

음.. 뭐랄까 INF 여야 하는 이유? 와 어떤 상황에서 두 코드가 차이가 나게 되는지 궁금합니다.

반례 TC 는 드립니다.

3 5

001

101

001

011

000

#include<iostream>
#include<vector>
#include<queue>
#include<utility>

using namespace std;
void BFS(int,int);

vector<vector<int> >map;
vector<vector<int> >Distmap;

int N = 0, M = 0, dy[4] = {-1,0,1,0}, dx[4] = {0,1,0,-1};

int main()
{
    string input;
    cin >> M >> N;
    map.resize(N,vector<int>(M,0));
    Distmap.resize(N,vector<int>(M,0));

    for(int i=0; i<N; ++i){
        cin >> input;
        for(int j=0; j<input.size(); ++j){
            map[i][j] = input[j]-48;
            Distmap[i][j] = 987654321;
        }
    }
    BFS(0,0);
    cout << Distmap[N-1][M-1] << "\n";
    return 0;
}

void BFS(int y, int x)
{
    int newy, newx;
    queue<pair<int,int> >Q;
    pair<int,int>block;
    Q.push(make_pair(y,x)); Distmap[y][x] = 0;

    while(!Q.empty())
    {
        block = Q.front(); Q.pop();

        for(int i=0; i<4; ++i)
        {
            newy = block.first + dy[i];
            newx = block.second + dx[i];

            if(newy < 0 || newx < 0 || newy >= N || newx >= M) continue;

            if(map[newy][newx] == 1)
            {
                if(Distmap[newy][newx] > Distmap[block.first][block.second]+1){
                    Distmap[newy][newx] = Distmap[block.first][block.second]+1;
                    Q.push(make_pair(newy,newx));
                }
            }
            else
            {
                if(Distmap[newy][newx] > Distmap[block.first][block.second]){
                    Distmap[newy][newx] = Distmap[block.first][block.second];
                    Q.push(make_pair(newy,newx));
                }
            }
        }
    }
}

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

문제

문제

출처

ICPC

정답은 맞췄으나 두 코드가 어떻게 다른지 자세하게 설명 주실분?

khndhkx123 4년 전 0

khndhkx123 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말