[ BOJ 1941 ] 소문난 칠공주

문제

친목하기 위해 7명의 그룹을 만드는데, 지배하기 위해 공주파가 최소 4명있어야한다.

5*5 행렬에서 얼마나 많은 그룹을 만들 수 있을것인가?

해설

백트래킹 기법을 이용하는데, 조금 창의적으로 활용한다.

이 문제를 풀기 위해 미리 알고 있으면 좋은 문제는 유명한 로또 문제이다.

7/45 로또 아님 ㅎ

로또 문제의 링크는 다음과 같다

http://icpc.me/6603

이 문제는 주어진 수 집합(7~9개) 중 7개를 고르는 문제이다.

이걸 활용한다.

일단 5*5로 되어있는 행렬을 한줄로 펼치고, 차례대로 인덱스를 붙이자.

(0,0)에 있는건 0, (0,1)에 있는건 1.... 이렇게

(i,j)에 있는건 5*i+j의 인덱스를 가지게 된다.

그 다음 로또에서 사용했던 백트래킹 기법으로 7개를 뽑는다.

뽑은 후에 우리가 볼건 2가지

1) 공주파가 4명 이상인가?

2) 서로 붙어있는가?

1번은 처음 입력받은거에서 가져오면 될것이다.

2번은 set에 7개의 좌표를 모두 넣어놓은 다음에, bfs롤 돌린다.

만약 bfs를 통해 7개의 좌표를 모두 방문했으면 다 연결되어있다는 뜻이다.

1번과 2번을 모두 만족하면 +1

코드는 다음과 같다

코드

#include <bits/stdc++.h>
#pragma warning (disable : 4996)
using namespace std;
char s[6][6];
int v[26];
int ans[27];
int cnts = 0;
int dx[4] = { -1,0,1,0 }, dy[4] = { 0,1,0,-1 };
void backtracking(int l,int cnt)
{
    if (cnt == 7)
    {
        int can = 0;
        for (int i = 0; i < 7; i++) can += v[ans[i]];
        if (can < 4) return;
        set<int> st;
        for (int i = 0; i < 7; i++) st.insert(ans[i]);
        bool visit[27] = { 0 };
        int tmp = 0;
        queue<int> bfs;
        bfs.push(ans[0]);
        while (!bfs.empty())
        {
            int tp = bfs.front();
            bfs.pop();
            if (visit[tp]) continue;
            visit[tp] = true;
            tmp++;
            for (int i = 0; i < 4; i++)
            {
                int sx = tp / 5, sy = tp % 5;
                if (sx + dx[i] < 0 || sx + dx[i] >= 5 || sy + dy[i] < 0 || sy + dy[i] >= 5) continue;
                int wantto = (sx + dx[i]) * 5 + sy + dy[i];
                if (st.find(wantto) != st.end()) bfs.push(wantto);
            }
        }
        if (tmp == 7) cnts++;
        return;
    }
    for (int i = l + 1; i <= 24; i++)
    {
        ans[cnt] = i;
        backtracking(i, cnt + 1);
    }
}
int main()
{
    for (int i = 0; i < 5; i++) scanf("%s", s[i]);
    for (int i = 0; i < 5; i++) for (int j = 0; j < 5; j++) v[i * 5 + j] = (s[i][j] == 'S' ? 1 : 0);
    backtracking(-1, 0);
    return !printf("%d", cnts);
}