[ 백준 1941 ] 소문난 칠공주 (C++)

백준의 소문난 칠공주(1941) 문제이다.

( 문제 바로가기 )

[ 문제풀이 ]

1) 문제의 전체적인 풀이 방법이나 접근하는 방법이 쉬운문제인 반면에 실제 구현하기에는 살짝 까다롭고 복잡한 부분이

   있는 문제이다.

   처음부터 하나하나씩 알아가면서 같이 풀어보도록 하자.

   우리가 구현해야 될 순서에 대해서 먼저 정리 해보고, 그 순서대로 풀이를 알아가보자.

   < 문제풀이 순서 >

    1. 총 25명의 학생 중에서, 7명을 뽑기 !

       - (본문함수 : DFS())

    2. 1번 만족시, 뽑은 7명 중에서, 이다솜파 학생이 적어도 4명 이상 있는지 확인 !

       - (본문함수 : bool MoreThanFour())

    3. 2번 만족시, 그 7명이 서로 인접해 있는지

       - (본문함수 : bool Adjacency())

   나도 몰랐는데 이렇게 적어놓으니 정말 간단한 문제같아 보인다.

 

2) 문제풀이 순서에 맞게 1번부터 풀이를 알아가보자.

   25명 중에 7명을 뽑는 문제이다. 당연히 이 문제는 조합을 구해야 하는 문제이다.

   { 1, 2, 3, 4, 5, 6, 7 } 번 학생이 칠공주가 되던, { 7, 2, 4, 1, 6, 3, 5 } 번 학생이 칠공주가 되던 결국 똑같은 것이기 때문에

   순서에 상관 없는 조합을 구하는 문제이다.

   조합을 구하는 방법을 잘 모른다면 → [ 조합 구현 구체적으로 알아보기(Click) ]

  

   본인은 25명 중에 7명을 뽑아야 하므로, 전체 25명을 0번 ~ 24번 까지 번호를 붙여주었다.

   따라서 Select[] 배열의 크기를 25로 잡고 그 중에 7명을 뽑는 조합으로 코드를 구현하였다.

   위의 글을 읽어보고 왔다면, 이 부분은 어렵지 않게 구현했을 것이다.

   2번 풀이로 가보자.

   우리는 현재 7명을 뽑았으니, 그 7명 중에서 이다솜파가 4명 이상인지 확인을 해야한다.

   그렇다면, 우리가 뽑은 번호의 좌표를 알아야 한다.

   만약에 { 1, 2, 3, 4, 5, 6, 7 } 번을 뽑았다면, 1번이 (x, y)로 나타내면 어디좌표인지 를 알아야지 뽑은 번호가

   이다솜파인지 임도연파인지 알 수 있기 때문이다.

   아래의 표를 보고 해당 번호와 좌표를 확인해보자.

 

   우리가 뽑은 번호를 좌표로 바꾸는 방법이 있다. 바로 한 변의 길이로 나눈 값이 x좌표, 나눈 나머지 값이 y좌표이다.

   0 번에 적용시켜보자. 한 변의 길이 = 5.

   x좌표 = 0 / 5 = 0

   y좌표 = 0 % 5 = 0 으로 0번을 좌표로 바꾸면 (0, 0)이 된다.

  11번에 적용시켜보자. 한 변의 길이 = 5.

  x좌표 = 11 / 5 = 2

  y좌표 = 11 % 5 = 1 따라서 11번은 (2, 1)이 된다. 이 방법을 통해서 우리는 해당 번호를 좌표로 바꿔줘야 한다.

 

  다시, 문제로 돌아와서... 우리가 번호를 좌표로 바꾼 이유는 이다솜파가 4명 이상인지를 확인하기 위해서이다.

  우리는 선택한 번호를 좌표로 바꿀 수 있고, 해당 좌표가 이다솜파인지 임도연파인지 입력으로 받아놨기 때문에

  이다솜파 학생수를 Count할 수가 있다.

  Count해서 조건에 만족하는 경우라면 3번 풀이과정으로, 아니라면 다시 조합으로 돌아가서 다른 7명의 경우를

  뽑아줘야 한다.

  마지막 3번이다. 우리는 현재까지 25명중에 7명을 뽑았고, 그 7명 중에 이다솜파가 4명 이상인 경우에만 이 과정을 진행

  하도록 이전에 구현해놓았다.

  본인은 이 문제를 BFS를 통해서 풀이를 하였다. 본문 함수(bool Adjacency() 참고하면서 읽을 것 !)

  본인은 크게 2개의 Check 함수를 사용하였다. 보통 BFS에서는 해당 정점을 탐색했는지 안했는지 Check하는 배열 하나만

  필요하지만, 이 문제의 경우 내가 선택한 학생들에 대해서만 탐색을 해야하기 때문에, 먼저 내가 선택한 학생들만 따로

  Check_Select[][] 라는 2차원 배열에 체크해주었다.

  또한 이 과정에서, 가장 먼저 나오는 학생의 좌표만 Queue에 저장해주었다. BFS를 실행하기 위해서는 시작점이 필요하기

  때문이다.

 

  BFS에서는 위에서 저장해둔 학생좌표를 시작으로, 인접한 곳으로 탐색을 진행하는데 이 때 생각해줘야할 조건으로는

  1. 내가 25명 중에 7명을 뽑았는데, 그 7명에 해당되는 학생인가?

  2. 그 7명에 해당되는 학생인데, 아직 탐색한 적이 없는 학생인가?

  이렇게 2가지 경우에 대해서 BFS를 탐색하면서, 탐색이 가능할 때마다 Count를 해주고, 그 Count한 값이 7이 된다면

  조건에 부합하기 때문에 종료시키면 된다.

  생각보다 구현할 내용이 많지만, 그리 어려운 문제는 아니라고 생각한다. 한 단계 한 단계 천천히 읽어보면서 따라한다면

  금방 풀 수 있을 것이다.

[ 소스코드 ]

#include<iostream>
#include<cstring>
#include<string>
#include<queue>
 
#define endl "\n"
using namespace std;
 
int MAP[5][5], Answer;
bool Select[25];
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1 ,0, 0 };
 
void Input()
{
    for (int i = 0; i < 5; i++)
    {
        string Inp;
        cin >> Inp;
        for (int j = 0; j < Inp.length(); j++)
        {
            if (Inp[j] == 'Y') MAP[i][j] = 1;
            else if (Inp[j] == 'S') MAP[i][j] = 2;
        }
    } 
}
 
bool MoreThanFour()
{
    int Cnt = 0;
    for (int i = 0; i < 25; i++)
    {
        if (Select[i] == true)
        {
            int x = i / 5;
            int y = i % 5;
 
            if (MAP[x][y] == 2) Cnt++;
        }
    }
    if (Cnt >= 4) return true;
    else return false;
}
 
bool Adjacency()
{
    queue <pair<int, int>> Q;
    bool Check_Select[5][5];
    bool Queue_Select[5][5];
    bool Check_Answer = false;
 
    memset(Queue_Select, false, sizeof(Queue_Select));
    memset(Check_Select, false, sizeof(Check_Select));
 
    int Tmp = 0;
    for (int i = 0; i < 25; i++)
    {
        if (Select[i] == true)
        {            
            int x = i / 5;
            int y = i % 5;
            Check_Select[x][y] = true;
 
            if (Tmp == 0)
            {
                Q.push(make_pair(x, y));
                Queue_Select[x][y] = true;
                Tmp++;
            }
        }
    }
 
    int Cnt = 1;
    while (Q.empty() == 0)
    {
        int x = Q.front().first;
        int y = Q.front().second;
        Q.pop();
 
        if (Cnt == 7)
        {
            Check_Answer = true;
            break;
        }
 
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if (nx >= 0 && ny >= 0 && nx < 5 && ny < 5)
            {
                if (Check_Select[nx][ny] == true && Queue_Select[nx][ny] == false)
                {
                    Queue_Select[nx][ny] = true;
                    Q.push(make_pair(nx, ny));
                    Cnt++;
                }
            }
        }
    }
 
    if (Check_Answer == true) return true;
    return false;
}
 
void DFS(int Idx, int Cnt)
{
    if (Cnt == 7)
    {
        if (MoreThanFour() == true)
        {
            if (Adjacency() == true) Answer++;
        }
        return;
    }
 
    for (int i = Idx; i < 25; i++)
    {
        if (Select[i] == true) continue;
        Select[i] = true;
        DFS(i, Cnt + 1);
        Select[i] = false;
    }
}
 
void Solution()
{
    DFS(0, 0);
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}