글 읽기 - 맞았는데 .. 왜 맞았는지.. 좀 찝찝합니다...

kyoungin 5년 전 0

고슴도치가 물이 될 곳은 갈 수 없다고 조건이 나와있어서,

물을 먼저 처리해주고 그다음에 고슴도치를 처리해주는 코드로 짰었는데 계속 틀리다가,

둘의 순서를 바꿔주니까 맞았네요..

왜 전자는 틀리고, 후자는 맞았는지 잘 개념이 잡히지 않습니다 ㅠㅠ

아시는 분 도움 주실수 있나요?

코드 두개 올리겠습니다

//맞은 코드 
void bfs(){
    
    
    while(!q.empty()){
        int i,j;

        int len= (int)q.size();
        for(j=0;j<len;j++){
            int y=q.front().first;
            int x=q.front().second;
            q.pop();
            if(v[y][x]!='S') {
                continue;
            }
            for(i=0;i<4;i++){
                if(y+dy[i]<0 || y+dy[i]>=r ||x+dx[i]<0 || x+dx[i]>=c )
                    continue;
                if(v[y+dy[i]][x+dx[i]]=='D'){
                    cout << cnt[y][x]+1 << '\n';
                    check=1;
                    return;
                }
                if(v[y+dy[i]][x+dx[i]]=='.' ){
                    q.push(p(y+dy[i],x+dx[i]));
                    v[y+dy[i]][x+dx[i]]='S';
                    cnt[y+dy[i]][x+dx[i]] =cnt[y][x]+1;
                }
            }
        }
        
        int wcnt=(int)water.size();
        for(j=0;j<wcnt;j++){
            int wy=water.front().first;
            int wx=water.front().second;
            water.pop();
            
            for(i=0;i<4;i++){
                
                if(wy+dy[i]<0 || wy+dy[i]>=r ||wx+dx[i]<0 || wx+dx[i]>=c )
                    continue;
                if(v[wy+dy[i]][wx+dx[i]] == '.' || v[wy+dy[i]][wx+dx[i]] == 'S'){
                    water.push(p(wy+dy[i],wx+dx[i]));
                    v[wy+dy[i]][wx+dx[i]] ='*';
                }
            }
        }// 물 채우기
        
    } //while
    
    if(check==0){
        err();
        return;
    }
    
}

//틀린 코드
void bfs(){
    
    
    while(!q.empty()){
        int i,j;
        //~물 
        int wcnt=(int)water.size();
        for(j=0;j<wcnt;j++){
            int wy=water.front().first;
            int wx=water.front().second;
            water.pop();
            
            for(i=0;i<4;i++){
                if(wy+dy[i]<0 || wy+dy[i]>=r ||wx+dx[i]<0 || wx+dx[i]>=c )
                    continue;
                if(v[wy+dy[i]][wx+dx[i]] == '.' || v[wy+dy[i]][wx+dx[i]] == 'S'){
                    water.push(p(wy+dy[i],wx+dx[i]));
                    v[wy+dy[i]][wx+dx[i]] ='*';
                }
                
            }
        }// 물 채우기
        
        // ~고슴도치
        int len= (int)q.size();
        for(i=0;i<len;i++){
            int y=q.front().first;
            int x=q.front().second;
            q.pop();
           if(v[y][x]!='S') {
                continue;
            }
            
            for(i=0;i<4;i++){
                if(y+dy[i]<0 || y+dy[i]>=r ||x+dx[i]<0 || x+dx[i]>=c )
                    continue;
                if(v[y+dy[i]][x+dx[i]]=='D'){
                    cout << cnt[y][x]+1 << '\n';
                    check=1;
                    return;
                }
                if(v[y+dy[i]][x+dx[i]]=='.' ){
                    q.push(p(y+dy[i],x+dx[i]));
                    v[y+dy[i]][x+dx[i]]='S';
                    cnt[y+dy[i]][x+dx[i]] =cnt[y][x]+1;
                }
            }
        }//고슴도치
        
    } //while
    
    if(check==0){
        err();
        return;
    }
    
}

luniro 5년 전 1

후자의 방식으로 하려면 88번째 줄의 조건을 제거해야합니다

3 3
...
DS*
...

기존 방식으로는 이런식으로 물과 붙어있는경우 무시됩니다

kyoungin 5년 전 0

@luniro

지웠는데도 안되네요 ㅠㅠ 또 다른 문제가 있을까요,,?

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

문제

문제

출처

ICPC

맞았는데 .. 왜 맞았는지.. 좀 찝찝합니다...

kyoungin 5년 전 0

luniro 5년 전 1

kyoungin 5년 전 0

@luniro

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말