[BOJ] 1941 - 소문난 7공주 / C++

문제

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

1941번: 소문난 칠공주

 

아이디어

1) 조합을 이용하여 7개의 좌표 선택
2) BFS를 이용하여, 선택한 좌표가 서로 연결되어 있는지 확인
3) 만약 연결되어 있을 시에는, 연결된 좌표들의 'S'의 개수와 'Y'의 개수 비교

 

처음에는 1)과 같이 조합을 이용하지 않고 백트래킹을 이용하여, 영역을 넓혀 나가며 좌표를 선택하다가 7개 모두 선택 시  2)와 3)의 과정을 수행하였다. 그러나 백트래킹으로는 십자 모양과 같이 두 축이 교차하는 형태는 찾아내지 못했기에, 일단 조합을 통해 7개의 좌표를 얻어내고 이후 해당 좌표가 연결된 좌표인지 BFS를 통해 판별하는 방법으로 변경하였다.

 

조합 구현에 대해 정리한 글

https://taehun0933.tistory.com/18

[알고리즘] next_permutation - 순열과 조합 / C++

 

또한 BFS를 통해 좌표가 연결되어 있는지 확인하는 과정에서, 기존 BFS의 조건 중 하나인 '방문 여부 확인' 말고도, '현재 탐색하는 좌표값이 조합을 통해 선택된 좌표값인지'에 대한 조건이 추가로 필요했다.

때문에 isCombinated 변수를 추가로 할당해 주었다.

 

next_permutation을 통한 조합으로 얻어낸 좌표값들을 isConnected함수에 넘겨 주어 연결 여부를 확인하였다.

또한 연결 여부를 확인하기 위해 BFS를 하는 과정에서

탐색하는 좌표값의 seats에 대응되는 값이 S인지 Y인지도 같이 확인해 주었다.

 

코드

#include <bits/stdc++.h>
using namespace std;

char seats[5][5];
int nums[25];
// 조합을 통해 0부터 24까지의 값 중 7개의 값을 얻어낼 변수.
// (해당 값 / 5) 그리고 (해당 값 % 5)가 각각 좌표에서의 x,y에 대응된다.

int numOfY;
int numOfS;
int res;

bool isVisited[5][5]; // 현재 탐색 중인 좌표의 방문 여부를 나타내는 변수.
bool isCombinated[5][5]; // 현재 탐색 중인 좌표가 조합 상의 값인지를 판단하는 변수.
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

#define X first
#define Y second

void scanSOrY(int x, int y)
{ // 입력받은 좌표에 해당하는 값에 따라 S 또는 Y의 개수를 증가시켜주는 함수.
    if (seats[x][y] == 'S')
        numOfS++;
    else
        numOfY++;
}

void init()
{ // 전역변수인 isVisited, isCombinated를 초기화시켜주는 함수.
    for (int i{0}; i < 5; i++)
        for (int j{0}; j < 5; j++)
        {
            isVisited[i][j] = false;
            isCombinated[i][j] = false;
        }
}

bool isConnected(vector<pair<int, int>> coords)
// BFS를 통해 좌표들이 연결되어있는지 확인하는 함수.
// 동시에 scanSOrY를 통해 해당 좌표값이 Y인지 S인지도 확인함.
{
    queue<pair<int, int>> q;
    scanSOrY(coords[0].X, coords[0].Y);
    q.push({coords[0].X, coords[0].Y});
    init();
    isVisited[coords[0].X][coords[0].Y] = true;

    for (int i{0}; i < coords.size(); i++)
        isCombinated[coords[i].X][coords[i].Y] = true;
        // 넘겨받은 조합 상의 7개 좌표값들만을 true로 만들어준다.

    while (!q.empty())
    {
        pair<int, int> cur = q.front();
        q.pop();

        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 (isVisited[nx][ny] || !isCombinated[nx][ny])
                continue;

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

    for (int i{0}; i < coords.size(); i++)
        if (!isVisited[coords[i].X][coords[i].Y])
            return false;
    return true;
    // 만약 넘겨받은 좌표값들의 isVisited가 모두 true라면
    // 넘겨받은 좌표값들이 모두 연결됨 -> isConnected == true
    // 그렇지 않다면 isConnected == false 리턴.
}

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

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

    fill(nums, nums + 25, 1);
    for (int i{0}; i < 7; i++)
        nums[i] = 0;

    do
    {
        vector<pair<int, int>> coords; // 조합을 통해 완성된 좌표값을 담을 벡터
        for (int i{0}; i < 25; i++)
            if (nums[i] == 0)
            {
                int num = nums[i] + i;
                int x = num / 5;
                int y = num % 5;
                coords.push_back({x, y});
            }

        // coords에 해당하는 좌표값을 다 담았으니
        // 이제 isConnected를 통해 이 값들이 연결되어있는지 확인.
        numOfY = 0;
        numOfS = 0;
        if (isConnected(coords) && numOfS > numOfY)
            res++;
           	// 연결되어 있으면서 동시에 S의 수가 Y의 수보다 많다면 1 증가.
    } while (next_permutation(nums, nums + 25));
    cout << res;
}