[C++] BOJ 1941 / 백트래킹 (소문난 칠공주, next_permutation 사용)

문제 분석

 

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

25명의 여학생들 중에 문제 조건에 맞는 인접한 그룹의 경우의 수를 출력하는 문제이다.

주어진 조건은

1. 여학생 수가 7명이어야 한다

2. 7명은 가로나 세로로 인접해 있어야 한다.

3. 7명 전부 이다솜파 일 필요는 없다.

4. 최소 이다솜파가 4명 이상은 반드시 포함되어야 한다.

 

해결 방법

1. 총 25명 학생 중에서 7명을 뽑아야 한다. (1번 조건 충족 시키기) - next_permutation 사용

2. 7명 중에 이다솜파가 4명 이상 있는지 확인한다. (4번 조건 충족 시키기)

3. 7명이 서로 인접해 있는지 확인한다. (2번 조건 충족 시키기) - BFS 사용

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
using namespace std;
#define X first
#define Y second
char board[5][5];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
int a[25];
int vis[5][5];
int chkSelect[5][5];
vector<pair<int,int>> v;

bool func() {
    int cntS=0;
    int cnt=0;
    queue<pair<int,int>> q;
    // 다솜파 4명 이상인지 체크
    for(int i=0;i<v.size();i++) {
        pair<int,int> cur = v[i];
        if(board[cur.X][cur.Y] == 'S') cntS++;
    }
    if(cntS < 4) return false;

    q.push({v[0].X, v[0].Y});
    vis[v[0].X][v[0].Y] = 1;
    while(!q.empty()) {
        pair<int,int> cur = q.front();
        q.pop();
        cnt++;
        for(int dir=0;dir<4;dir++) {
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];
            if(nx < 0 || ny < 0 || nx >= 5 || ny >= 5) continue;
            if(vis[nx][ny] || !chkSelect[nx][ny]) continue;
            q.push({nx,ny});
            vis[nx][ny] = 1;
        }
    }
    if(cnt == 7) return true;
    else return false;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int ans=0;
    for(int i=0;i<5;i++) {
        for(int j=0;j<5;j++) {
            cin >> board[i][j];
        }
    }
    fill(a, a+25, 1);
    for(int i=0;i<7;i++) {  // 25개 중에 7개를 뽑는 조합
        a[i] = 0;
    }
    do {
        int index=0;
        for(int i=0;i<25;i++) {
            if(a[i] == 0) {
                v.push_back({i/5, i%5});
                chkSelect[i/5][i%5] = 1;
            }
        }
        if(func()) 
            ans++;
        for(int i=0;i<5;i++) {
            fill(chkSelect[i], chkSelect[i] + 5, 0);
            fill(vis[i], vis[i]+5, 0);
        }
        while(!v.empty()) {
            v.pop_back();
        }
    }while(next_permutation(a, a+25));

    cout << ans;

}

 

- next_permutation

필요한 헤더파일은<algorithm>이다.

#include <algorithm>

int a[4] = {1,2,3};
do{
	for(int i = 0; i < 3; i++)
    	cout << a[i];
    cout << '\n';
}while(next_permutation(a, a+3));

/*
123
132
213
231
312
321
*/

next_permutation은 현재의 수열을 사전 순으로 생각했을 때의 다음 수열로 만들고 true를 반환하는 함수이다.

현재가 1 2 3이면 next_permutation을 한 번 실행한 후 1 3 2가 되고, 1 3 2에서 next_permutation을 실행하면 2 1 3이 된다. 만약 현재의 수열이 사전 순으로 생각 했을 때 제일 마지막이어서 다음 수열이 존재하지 않는다면 false를 반환한다. 그렇기 때문에 do-while 문으로 작성하면 코드가 깔끔하게 떨어진다.

 

위의 경우에는 순열이고 조합(순서 없이 뽑는)의 경우도 구현 가능하다.

#include <algorithm>

int a[5] = {1,2,3,4,5};
int ch[5] = {0,0,0,1,1};
do{
	for(int i = 0; i < 5; i++)
    	if(!ch[i])
    		cout << a[i];
    cout << '\n';
}while(next_permutation(a, a+3));

이런 식으로 0, 1을 넣은 배열로 if문을 사용하여 뽑을 수 있다.

 

이번 문제를 풀면서 경험했던 주의할 점으로는, 전역 변수로 배열을 선언하면 '0'으로 초기화 되는 성질 때문에 ch 배열을 초기화를 따로 진행 하지 않고 1로써 조합을 구현하려 했는데 오류가 났다. 전역 변수로 선언했을 때의 초기화 되는 0은 숫자 0이랑 또 다른 개념인 듯 하다. 이에 대해서는 추후에 추가 포스팅을 하며 정리해야 겠다.

 

참고 링크

https://blog.encrypted.gg/945?category=773649