백준 g3 1941 소문난 칠공주 c++

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

1941번: 소문난 칠공주

 

풀이

DFS는 ㅜ자 형태의 경로가 안 된다.

전체 25자리 중 7자리를 고르는 25C7을 해도 충분히 시간 제한 안에 풀 수 있다.

 

next_permutation을 통해 25C7를 구하고, Y의 개수가 4개를 넘거나 인접하지 않으면 continue 하도록 했다

서로 인접해있는지는 BFS로 풀었고, prin 한 명을 시작점으로 해서 area가 7이 되지 않으면 인접하지 않다는 뜻이므로 false를 return했다.

 

소스 코드

/*boj g3 1941 소문난 칠공주*/
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>

#define MAXN 6
using namespace std;

int N;
int answer = 0;
string board[MAXN];
vector<int> choice;

int prin[MAXN][MAXN];
int vis[MAXN][MAXN];

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

void printVis() {
    cout << "\n=========================\n";
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++) {
            cout << prin[i][j] << " ";
        }
        cout << "\n";
    }
}

void initialize() {
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++) {
            prin[i][j] = 0;
            vis[i][j] = 0;
        }
    }
}

pair<int, int> start;
void vecToPrin() {
    for (int i = 0; i < 25; i++) {
        if (choice[i] == 0) {
            int x = i / 5;
            int y = i % 5;

            prin[x][y] = 1;

            start.first = x;
            start.second = y;
        }
    }
}

int getYCnt() {
    int YCnt = 0;

    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++) {
            if (prin[i][j] == 1) {
                if (board[i][j] == 'Y')
                    YCnt++;
            }
        }
    }

    return YCnt;
}

bool isAdj() { // 서로 인접해 있는지
    queue<pair<int, int>> Q;

    vis[start.first][start.second] = 1;
    Q.push({start.first, start.second});
    int cnt = 0;

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

        for (int dir = 0; dir < 4; dir++) {
            int nx = cur.first + dx[dir];
            int ny = cur.second + dy[dir];

            if (nx < 0 || nx >= 5 || ny < 0 || ny >= 5) continue;
            if (vis[nx][ny] > 0) continue;
            if (prin[nx][ny] == 0) continue;

            vis[nx][ny] = vis[cur.first][cur.second] + 1;
            Q.push({nx, ny});
        }
    }

    if (cnt == 7)
        return true;
    else
        return false;
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    for (int i = 0; i < 5; i++) {
        cin >> board[i];
    }

    for (int i = 0; i < 7; i++)
        choice.push_back(0);
    for (int i = 0; i < 18; i++)
        choice.push_back(1);

    do {
        initialize();
        vecToPrin();

        if (getYCnt() >= 4) continue;
        if (!isAdj()) continue;
        // printVis();
        answer++;
    } while (next_permutation(choice.begin(), choice.end()));

    cout << answer << '\n';
}