글 읽기 - AC는 받았는데 질문이 있습니다...ㅠㅠ

stajw 3년 전 0

bfs로 문제를 풀었는데

43번째 줄에서 현재 칸의 check값이 distance보다 작을때만 갱신한다는 조건을 왜 넣어주어야 하는지 모르겠습니다.

43-44번째 줄을 조건문 없이 그냥 distance = check[tmpx+mx[i]][tmpy+my[i]] 로 바꾸면 답이 다르게 나옵니다.

어차피 bfs면 check값이 같은 칸들만 쭉 들어오고 check값이 1 증가한 칸이 들어올때는 32번째 줄에서 break를 시켜주는데 왜 조건을 굳이 넣어주어야 하는지 이해가 안됩니다ㅠㅠ 도움 부탁드립니다ㅠㅠ

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

using namespace std;

int n;
int arr[20][20] = {0};
int check[20][20] = {0};
int startx, starty;
int flag = 0;
int ans = 0;
int size = 2;
int mx[4] = {0,0,1,-1};
int my[4] = {1,-1,0,0};

bool isin(int x, int y){
    if(x<0 || x>=n || y<0 || y>=n) return false;
    return true;
}

void bfs(int x, int y){
    int distance = 9999999;
    int nextx = 999999;
    int nexty = 999999;
    queue<pair<int,int>> q;
    q.push(make_pair(x,y));
    check[x][y] = 1;
    while(!q.empty()){
        int tmpx = q.front().first;
        int tmpy = q.front().second;
        if(check[tmpx][tmpy] > distance) break;
        q.pop();
        for(int i=0; i<4; i++){
            if(check[tmpx+mx[i]][tmpy+my[i]] != 0) continue;
            if(isin(tmpx+mx[i],tmpy+my[i]) == false) continue;
            if(arr[tmpx+mx[i]][tmpy+my[i]] > size) continue;
            
            q.push(make_pair(tmpx+mx[i],tmpy+my[i]));
            check[tmpx+mx[i]][tmpy+my[i]] = check[tmpx][tmpy] + 1;
            
            if(size > arr[tmpx+mx[i]][tmpy+my[i]] && arr[tmpx+mx[i]][tmpy+my[i]] != 0){
                if(check[tmpx+mx[i]][tmpy+my[i]] <= distance) distance = check[tmpx+mx[i]][tmpy+my[i]];
                else continue;
                
                if(tmpx+mx[i] < nextx){
                    nextx = tmpx+mx[i];
                    nexty = tmpy+my[i];
                }
                else if(tmpx+mx[i] == nextx){
                    if(tmpy+my[i] < nexty){
                        nextx = tmpx+mx[i];
                        nexty = tmpy+my[i];
                    }
                }
            }
        }
        
    }
    if(nextx != 999999 || nexty != 999999){
        flag++;
        arr[x][y] = 0;
        arr[nextx][nexty] = 0;
        ans += distance-1;
        startx = nextx;
        starty = nexty;
    }
    
}

void solve(){
    while(1){
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++) check[i][j] = 0;
        }
        int tmpflag = flag;
        bfs(startx, starty);
        if(tmpflag == flag) return;
        
        if(flag == size){
            flag = 0;
            size++;
        }
    }
}

int main(){
    cin >> n;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++) cin >> arr[i][j];
    }
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(arr[i][j] == 9){
                startx = i;
                starty = j;
                break;
            }
        }
    }
    solve();
    cout << ans;
}

aftersnow 3년 전 0

32번째 줄을 아래와 같이 변경해야 합니다.

if(check[tmpx][tmpy] >= distance) break;

만약에 distance 가 7인데 현재 탐색하려는 check[tmpx][tmpy] 도 7이면
조건 문에 안걸리고 작은 물고기를 찾아서 distance가 갱신됩니다.

예제 5번을 돌려보시면 될 것 같아요.

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

문제

문제

출처

ICPC

AC는 받았는데 질문이 있습니다...ㅠㅠ

stajw 3년 전 0

aftersnow 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말