글 읽기 - 문제 풀이

johyesong8686 3년 전 0

처음의 저의 접근 방법은

1. BFS를 돌며 더러운칸을 찾는다.

2. 만일 더러운 칸을 찾았으면 queue와 방문 배열을 초기화 하고 break하여 해당 지점을 다시 시작으로 BFS를 돌며 더러운 칸을 찾는다.

로 풀었습니다. 몇 풀이들을 보니까 그리디를 이용한것 같은데,

해당 풀이로 왜 안되는 지와 왜 그리디를 사용해야하는 지 알려주실 수 있을까요?

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

struct Point{
    int x;
    int y;
    int c;
};
int d_x[]={-1,1,0,0};
int d_y[]={0,0,-1,1};

int main() {
    while(true){
        int w,h;
        cin >>w >>h;
        if(w==0 && h==0){
            break;
        }
        int s_x,s_y;
        int cnt=0;
        string p[h+1];
        for(int i=0;i<h;i++){
            cin >>p[i];
            for (int j=0; j<p[i].size();j++){
                if(p[i][j]=='o'){
                    s_x=i;
                    s_y=j;
                }else if(p[i][j]=='*'){
                    cnt+=1;
                }
            }
         
        }
        
        queue <Point> q;
        q.push({s_x,s_y,0});
        int visited[h+1][w+1];
        memset(visited,-1,sizeof(visited));
        visited[s_x][s_y]=1;
        int ans=0;
        while(!q.empty()){
            int x=q.front().x;
            int y=q.front().y;
            int c=q.front().c;
            q.pop();
            if(cnt==0){
                             
                 break;
            }
            // cout<<"cur :" <<"x :"<< x <<" y :"<<y<<" time :"<<c<<'\n';
            for(int k=0; k<4;k++){
                int nx=x+d_x[k];
                int ny=y+d_y[k];
                 
                if(nx>=0 && nx <h &&ny>=0 && ny<w){
                    if(visited[nx][ny]==-1){
                        if(p[nx][ny]=='x') continue;
                        else if(p[nx][ny]=='*'){
                            // cout<<"find :" <<"nx :"<< nx <<" ny :"<<ny<<" time :"<<c+1<<'\n';
                            p[nx][ny]='.';
                            cnt-=1;
                            memset(visited,-1,sizeof(visited));
                            
                            queue <Point> temp;
                            temp.push({nx,ny,c+1});
                            q=temp;
                            
                            if(cnt==0){
                                ans=c+1;
                            }
                            break;
                        }else{
                            //  cout<<"nx :"<< nx <<" ny :"<<ny<<" time :"<<c+1<<'\n';
                             q.push({nx,ny,c+1});
                        }
                        
                         visited[nx][ny]=1;
                    }
                }
            }
            
        }
        if(cnt!=0){
            cout<<-1<<'\n';
        }else{
            cout<<ans<<"\n";
        }
        
        
    }
  
    return 0;
}

bok03220 3년 전 2

저도 처음엔 똑같이 접근했는데요.

3 3

...

.o*

***

이 경우 오른쪽을 먼저 탐색하게 되면 최소 이동 횟수인 4개가 나오지만

아래를 먼저 탐색하게 되면 5개가 나와 틀립니다.

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

문제

문제

출처

ICPC

문제 풀이

johyesong8686 3년 전 0

bok03220 3년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말