[C++] Boj 1941 소문난 칠공주

문제 링크

1941 소문난 칠공주

 

접근

 

문제를 풀다가 어떻게 풀어야 할지 긴가민가해서 알고리즘 분류 항목을 열어 훔쳐보았다...

열심히 생각해 본 결과는 아래와 같다.

1. 25C7을 구한다.
2. 7명이 접해 있는지 확인한다.
3. 7명이 접해 있다면, 이다솜파의 수가 4 이상일 때, ans를 카운트한다.

하지만 구현에는 실패하였다. 바킹독 님의 답안에는 next_permutation를 사용한 풀이가 있었지만, 나는 next_permutation에 대한 이해가 부족했다.

next_permutation에 대한 공부를 더 하고 이 문제를 이해해 보려 한다.

 

전체 코드

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

// 1. 25C7을 구함.
// 2. 7명이 접해있는지 확인
// 3. 이다솜파의 수 확인

// 공부해야 할 것
// 1. next_permutation 정확한 이해
// 2. 문제 답에 대한 정확한 이해

string board[5];

int ans;

// next_permutation
bool mask[25];

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

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

    for (int i = 0; i < 5; i++)
    {
        string str;
        cin >> str;

        board[i] = str;
    }

    // 25개 중 7개를 뽑으므로, 
    // mask 배열을 0 7개, 나머지는 1로 채운다. 
    fill(mask + 7, mask + 25, true);

    do
    {
        queue<pair<int, int>> q;
        int dasom = 0, cnt = 0;
        bool Is7[5][5] = {}, visited[5][5] = {};

        for (int i = 0; i < 25; i++)
        {
            if (mask[i] == 0)
            {
                int x = i / 5;
                int y = i % 5;

                Is7[x][y] = true;

                if (q.empty())
                {
                    q.push({ x, y });
                    visited[x][y] = true;
                }
            }
        }

        while (!q.empty())
        {
            int x = q.front().first;
            int y = q.front().second;

            q.pop();

            cnt++;

            dasom += board[x][y] == 'S';

            for (int k = 0; k < 4; k++)
            {
                int nx = x + dx[k];
                int ny = y + dy[k];

                if (nx < 0 || nx >= 5 || ny < 0 || ny >= 5) continue;
                if (visited[nx][ny] || !Is7[nx][ny]) continue;

                q.push({ nx, ny });
                visited[nx][ny] = true;
            }
        }

        ans += (cnt >= 7 && dasom >= 4);

    } while (next_permutation(mask, mask + 25));

    cout << ans;

    return 0;
}

 

분석

do
{
    queue<pair<int, int>> q;
    int dasom = 0, cnt = 0;
    bool Is7[5][5] = {}, visited[5][5] = {};

    .
	.
	.

} while (next_permutation(mask, mask + 25));

 

전체 틀은 25C7을 구하는 next_permutation을 이용한 do-while문이다.

7명이 인접해 있는지 확인할 때 bfs를 사용하므로, q를 선언하였다.

visited 배열은 bfs 탐색 시 사용한다.

Is7 배열은 7명 각각의 좌표를 표시하기 위해 사용한다.

 

for (int i = 0; i < 25; i++)
{
    if (mask[i] == 0)
    {
        int x = i / 5;
        int y = i % 5;

        Is7[x][y] = true;

        if (q.empty())
        {
            q.push({ x, y });
            visited[x][y] = true;
        }
    }
}

 

next_permutation의 mask 배열을 0이 7개, 1이 나머지로 구성하였으므로 mask[i]가 0일 때, 그 수를 뽑아 준다.

이때 mask 배열은 1차원 배열로 선언하였으므로 

                int x = i / 5;
                int y = i % 5;

 

와 같은 방법으로 2차원 배열의 좌표로 변환한다.

 

다음, 7명 배열에 좌표를 기록하고, q가 비어있으면 q에 push한다.

이것을 i==25까지 반복하면 Is7 배열은 7개가 true로 설정되어 있고, q에는 Is7의 최초 좌표만이 들어 있을 것이다.

 

while (!q.empty())
{
    int x = q.front().first;
    int y = q.front().second;

    q.pop();

    cnt++;

    dasom += board[x][y] == 'S';

    for (int k = 0; k < 4; k++)
    {
        int nx = x + dx[k];
        int ny = y + dy[k];

        if (nx < 0 || nx >= 5 || ny < 0 || ny >= 5) continue;
        if (visited[nx][ny] || !Is7[nx][ny]) continue;

        q.push({ nx, ny });
        visited[nx][ny] = true;
    }
}

ans += (cnt >= 7 && dasom >= 4);

 

이제 bfs 탐색을 한다. 

탐색을 할 때마다 인접해 있는 인원 수를 카운팅 해 주며, 그 사람이 이다솜파일 경우 따로 카운팅 해 준다.

다른 그래프 탐색 문제와 비슷하게 4방향으로 탐색해 준다.

이미 방문한 좌표거나, 그 좌표에 있는 사람이 Is7 배열에 속한 7명 중 한 사람이 아니라면 continue한다.

이렇게 하면 오로지 최초로 탐색된 인접한 사람만이 q에 들어갈 수 있는 것이다.

7명 중, 이 좌표와 4방향으로 인접한 사람이 없는 경우에는 q에 push된 게 없으므로 while문은 종료된다.

 

마지막으로 인접한 사람이 7명(이상)이며 이다솜파가 4명 이상일 경우 ans에 카운팅 한다.