백준 연구소 3 (17142) c++ BFS/ 문제풀이

https://www.acmicpc.net/problem/17142

17142번: 연구소 3

백준 문제 연구소 3을 풀었다.

 

처음에 문제를 보자마자 bfs 랑 브루트포스 알고리즘을 이용해서 풀게 되면 쉽게 해결할 수 있을것이라고 생각했다.

요즘 solved라는걸 친구가 백준이랑 연동시켜줘서 보는 재미가 솔솔하다 ㅎㅎ

그래서 가끔 문제 풀기전에 난이도를 보고 쫄기도하고 자신감있게 풀기도 한다 그래서 이번에도 한번 어느정도 난이도인지를 찾아보았다.

골드4였다. 골드 4정도야~라고 생각하고 문제를 읽었다.

그냥 흠.. 그동안 풀었던 방법들 활용해서 풀어야지하고 금방 문제를 풀었다.

 

문제풀이

1. 전체 바이러스중에서 M개의 바이러스를 중복없이 고르는 수열을 구하는 함수를구현하고

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

2. bfs 함수를 구현

3. 활성화되지 않은 바이러스를 처리하기

 

다음과 같은 틀을 잡고 코드를 짜기 시작했습니다.

모든 예제는 맞았으나,, 시간초과.. 풀이가 100맞다고 확신을 하였지만 컴퓨터는 거짓말하지 않는것을 알기에...

생각을하고 생각을하다가 결국 다른 분들의 코드를 for문의 갯수만 확인하자 하고 확인을 하였다.

갯수는 같았고 풀이도 얼추 비슷해보였다.

 

수열을 구현하는것을 당연히 맞다고 생각한 내가... 잘못이였다

대부분의 시간초과는 방문했던 곳을 다시 또 방문한다던가 이미 구했던 것들을 다시 또 구하는 등의 방식이 이루어지기 때문에

불필요한 재 방문이 시간초과를 만든다.. -> 본인은 이걸.. 생각안함.. 당연히 맞게 구현했다는 쓸데없는 자신감에.. 2일을 날렸다.

 

결국 다시 코드를 보았고 cout을 이용한 수열을 체크.. 당연 중복되게 나왔다.

그래서 수열을 다시 다음과 같이 수정하였다.

[잘못된 코드]

[올바른 코드]

void bruto(int num,int ind){

        //바이러스의 갯수만큼 일때

        

        if(num == M){

            for(int i=0;i<M;i++){

                q.push(make_pair(v[arr[i]].first,v[arr[i]].second));

                cnt[v[arr[i]].first][v[arr[i]].second]=0;

                visit[v[arr[i]].first][v[arr[i]].second]=1;

            }

     

            bfs();

           // memset(cnt, 0, sizeof(cnt));

            memset(visit,0,sizeof(visit));

            stop_cnt =0;

            return;

        }

      for(int i=0;i<v.size();i++){

                if( ind < i){

                    arr[num]=i;

                    bruto(num+1,i);

                }

            }

    }

 

이렇게 짜게 된다면 중복없이 수열이 나오게 된다.

 

 

    #include<iostream>

    #include<vector>

    #include<cstring>

    #include<algorithm>

    #include<queue>

 

    using namespace std;

 

    #define MAX_N 51

    int N , M; // 연구소 크기와 바이러스의 갯수

    int stop=0;

    int map[MAX_N][MAX_N];  //연구소 지도

    int x_dir[4]={-1,1,0,0};

    int y_dir[4]={0,0,-1,1};

    queue<pair<int,int>> q;

    vector<int> minv;

    vector<pair<int,int>>v;

    int arr[11];

    int visit[MAX_N][MAX_N];

    int visited[10];

    int cnt[MAX_N][MAX_N];

 

    int M_result =99999 ;

    int stop_cnt =0;

 

    void bfs();

    void bruto(int num,int ind);

 

    int main(){

        ios::sync_with_stdio(false);

        cin.tie(NULL);

        cout.tie(NULL);

        cin >> N >> M;

        for(int i=0;i<N;i++){

            for(int j=0;j<N;j++){

                int input;

                cin >> input;

                map[i][j]=input;

                if(input ==0 ) stop +=1;

                else if(input ==2){

                    v.push_back(make_pair(i,j));

                    }

            }

        }

        //움직일 수 있는 칸이 없을 때

 

        if(stop ==0 ){

            cout<< 0 <<"\n";

            return 0;

        }

        else{

            bruto(0,-1);

            if(minv.empty()==1) cout<<-1;

            else{

                cout<<*min_element(minv.begin(), minv.end());

                cout<<"\n";

            }

        }

        return 0 ;

    }

    void bfs(){

        int result=0;

        while(!q.empty()){

            int x = q.front().first;

            int y = q.front().second;

            q.pop();

            for(int i=0;i<4;i++){

                int nx = x + x_dir[i];

                int ny = y + y_dir[i];

                if(nx >=0 && ny >= 0 && nx < N && ny < N){

                    if(map[nx][ny]!=1 && visit[nx][ny]==0){

                        if(map[nx][ny]==0) {

                            stop_cnt+=1;

                        }

                    

                            cnt[nx][ny]=cnt[x][y]+1;

                     

                        visit[nx][ny]=1;

                        result = cnt[nx][ny];

                        q.push(make_pair(nx,ny));

                        if(stop_cnt==stop) {

                            minv.push_back(result);

                            while(!q.empty()){

                                q.pop();

                            }

                            

                        }

                 

                    }

                }

            }

        }

        

    }

 

bfs에서 주의해야할 것은 SW역량기출에서 상하좌우 움직이는 방법 그대로 구현하되 활성화 되지 않은 바이러스도 0과 같이 취급을 하되 빈공간을 움직인 횟수를 카운트하는 stop_cnt는 빈 공간일 때만 카운트를 해주는 것이 bfs에서는 중요했던것 같다.

 

또한, stop_cnt 가 빈공간의 갯수 stop이랑 같을 경우에만 minv에 push해주고 최종적으로 모든 순열의 경우들의 하고난뒤에 min_element를 이용하여 최소값을 출력할 수 있게하였다.

 

 

main과 bfs 구현이다. 주석이 없어 지저분하고.. 전역변수를 너무 많이 선언하여 코드가 지저분해보인다..

최대한 깔끔하게 짜도록.. 노력해야겠다.

 

순열 잘못된거를 찾고난뒤에 흥분해서 미친듯이 ㅋㅋㅋㅋ시도를했다 ㅋㅋㅋㅋㅋ

생각을 좀더 깊게하고 진행해야겠다.. 

다음은.. 치킨배달.. 메모리 초과.. 해결하는글로 찾아뵙겠습니다.