[BOJ] 1941번 : 소문난 칠공주 (C++)

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

1941번: 소문난 칠공주

 

이 문제를 보면 bfs로 7명이 서로 연결되어 있는지를 확인할 필요가 있다는 것은 알 수 있다. 

그런데 25명 중 그 7명을 어떻게 고를지를 고민해봐야한다. 

25명 중 7명을 뽑는 것이니 조합을 사용하면 된다. 

경우의 수가 많아보이지만, 25C7 = 480700 이므로 충분히 2초 안에 수행할 수 있다. 

그래서 문제를 풀 아이디어는 다음과 같다.

1. next_permutation 함수를 사용하여 25명 중 칠공주가 될 7명을 뽑는다.

2. 뽑힐 7공주가 모두 연결되어 있는 좌표인지 bfs를 돌려 탐색한다. 

3. 모두 연결되어 있다면 정답을 하나 늘린다. 

 

그런데 bfs를 돌리기 위해서는 시작점이 필요하고, 뽑힌 7명의 좌표가 저장되어 있어야 한다.

그래서 좀 더 구체적으로 아이디어를 적으면 아래와 같다. 

 

1. next_permutation 함수를 사용하여 25명 중 칠공주가 될 7명을 뽑는다.

2. 뽑은 7명의 좌표를 저장하면서 해당 좌표가 "S"인지 확인하고 카운트한다. (이 때 좌표는 x=i/5, y=i%5로 해주면 됨)

3. 큐가 비어있다면 bfs를 시작할 시작점 좌표 하나를 넣어준다.

4. 7개의 좌표를 모두 살펴본 결과, S의 개수가 4개보다 적으면 다솜파가 4명보다 적은 것이므로 탐색하지 않는다.

5. S의 개수가 4개 이상이라면 bfs로 탐색한다. 이 때, 큐에는 아까 넣은 시작점 좌표 하나가 있으니 이 좌표로 시작하면 된다. 

6. 큐에서 좌표를 꺼낼 때마다 adj 개수를 하나 늘려준다. 또한, 큐에 넣어주기 위해선 칠공주로 뽑힌 그 7개의 좌표 중 하나가 맞는지 확인해준다. 

7. 최종적으로 adj개수가 7개가 된 경우에는 모든 좌표가 연결되어 있는 것이므로 정답을 하나 늘려준다. 

 

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
#define X first
#define Y second

string board[5];
int permu[30]; //조합을 구할 때 사용될 배열 25개 중 7개는 0으로 채워짐
int ans=0; //답 카운트

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

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    for(int i=0; i<5; i++){
        cin>>board[i];
    }

    for(int i=0; i<30; i++) permu[i]=1;
    for(int i=0; i<7; i++) permu[i]=0;

    //25개 중 조합을 이용하여 7개를 뽑고 뽑은 정수를 좌표로 변환한다.
    //좌표를 저장하면서 해당 좌표가 S인지를 센다.
    //그 수에 해당하는 좌표들 중 "S"가 4개 이상이면 bfs를 돌린다.
    //그 후 모두 연결되어 있으면 답으로 센다.
    do
    {
        queue<pair<int,int>> q;
        bool visited[5][5]={0,}; //bfs를 돌려야 하므로 vis배열 필요
        bool isP7[5][5]={0,}; //조합을 통해 7명으로 뽑힌 사람의 좌표 표시
        int cntS=0; //"S"의 개수를 세는 변수 
        for(int i=0; i<25; i++){
            int x,y;
            if(permu[i]==0){
                x = i/5;
                y = i%5;
                isP7[x][y]=1;
                if(board[x][y]=='S') cntS++;

                if(q.empty()){ //시작점 하나를 큐에 넣어줌 
                    q.push({x,y});
                    visited[x][y]=1;
                }
            }
        }
        if(cntS<4) continue; //다솜파가 4명보다 적으면 탐색할 필요x

        int adj=0; //isP7로 연결돼있으면서 인접한 사람의 수를 저장 
        while(!q.empty()){
            auto cur = q.front();
            q.pop();
            adj++;

            for(int dir=0; dir<4; dir++){
                int nx = cur.X+dx[dir];
                int ny = cur.Y+dy[dir];

                if(nx<0||nx>5||ny<0||ny>=5) continue;
                if(visited[nx][ny]||!isP7[nx][ny]) continue;
                
                visited[nx][ny]=1;
                q.push({nx,ny});
            }
        }

        if(adj==7) ans++;
    } while (next_permutation(permu, permu+25));

    cout<<ans;
}

 

회고)

원래는 좌표를 2차원 배열에 저장하는 것이 아니라 큐에 바로 넣으려고 하였다. 그런데 큐에 넣으면 큐에서 좌표를 하나씩 지우면서 나아가니깐 옆에 좌표를 지우는 순간 붙어있던 좌표로 나아갈 수 없었다. 즉, 좌표를 큐에 넣고 지우는 아이디어는 말이 안됐다. 그럼 그 다음은 벡터에 저장해야 하나 생각해봤다. bfs에서 찾은 nx,ny를 벡터에 있는 좌표들 중 하나와 일치한지를 확인하려 했었다. 이렇게 되면 O(n)의 시간복잡도가 필요했다. 그런데 아예 2차원 배열로 바로 저장해주면 O(1) 만에 알 수 있었고, 시작점만 큐에 넣어주면 되었다.