[백준] 1941: 소문난 칠공주

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

1941번: 소문난 칠공주

이해하기에는 쉽지만 막상 구현하려고 하면 잘 안 풀린다.

왜냐하면 너무 오랜만에 푸는 DFS이기도 했고, 그동안 자주 접했던 DFS 문제와 살짝 달랐기 때문이다.

 

이전의 DFS는 한 줄로 구성되어, 한 점을 기준으로 주변을 탐색했다면 이 문제는 한 점이 아니라 7공주 그룹 전체를 중심으로 주변을 모두 탐색해야 했기 때문이다. 이와중에 중복을 제거하려고 하니 머리가 터졌다.

 

즉 이렇게 되면서 요구사항이 뒤엉키게 되었다.

 

그래서 요구사항부터 간결하게 정리하였다.

문제의 요구 사항

1. 총 25명의 학생 중에서 7명을 뽑는다.

2. 7명 중 이다솜파가 4명 이상이다.

3. 7명이 인접해있다.

 

우선 흔하게 해왔던 인접한 점을 이어나가는 DFS 탐색 방식이 아니라 조합의 방식으로 7개를 골라서 이 중 가로, 세로로 인접한 그룹만 뽑아내는 것이 간편하다. 조합을 위해 간편하게 bool타입의 1차원 배열을 활용하여 7공주 구성원을 파악함과 동시에 row, column을 파악하여 인접성까지 파악하도록 한다. 1차원 배열의 경우 0부터 24까지 번호를 매겨서 5로 나눈 몫과 나머지가 각각 row, column에 해당한다.

 

원래는 더 간단하게 처리하고 싶은 마음에 비트 연산자를 쓰려다가 너무 복잡해져서 그나마 bool 타입으로 타협을 보았다.

 

인접성(Adjacency)을 파악할 때는 우선 선택한 학생들만 따로 표시를 해두고, 그 학생들을 BFS(DFS여도 상관은 없다.) 알고리즘을 통해 상하좌우로 탐색하며 내가 선택한 학생이 인접해있는지, 그리고 이전에 확인했던 학생이 아닌지 체크를 한다.

 

이렇게 재귀 DFS를 통해 중복 없는 조합을 만들어 나가고 조건들에 부합하는 경우를 찾으면 경우의 수를 1씩 증가한다.

 

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
// 1은 이다솜파, 2은 임도연파
int map[5][5];
int answer = 0;
bool flat_board[25];
int dr[4] = {-1, 1, 0, 0};
int dc[4] = {0, 0, -1, 1};

bool bound(int r, int c) {
    return r >= 0 && r < 5 && c >= 0 && c < 5;
}
bool is_adjacent() {
    queue<pair<int, int>> q;
    // 내가 선택한 학생들만 입력
    vector<vector<bool>> check_select(5, vector<bool>(5, false));
    // 가장 먼저 나오는 학생의 좌표부터 BFS 탐색 시작
    vector<vector<bool>> queue_select(5, vector<bool>(5, false));

    bool first_pushed = false;
    bool finished = false;

    for(int i = 0;i < 25;i++) {
        if(flat_board[i] == true) {
            int r = i / 5;
            int c = i % 5;

            check_select[r][c] = true;
            if(!first_pushed) {
                q.push(make_pair(r, c));
                queue_select[r][c] = true;
                first_pushed = true;
            }
        }
    }

    int cnt = 1;
    while(!q.empty()) {
        int r = q.front().first;
        int c = q.front().second;

        q.pop();
        if (cnt == 7) {
            finished = true;
            break;
        }

        for(int i = 0;i < 4;i++) {
            int nr = r + dr[i];
            int nc = c + dc[i];

            if(bound(nr, nc)) {
                if(check_select[nr][nc] && !queue_select[nr][nc]) {
                    queue_select[nr][nc] = true;
                    q.push(make_pair(nr, nc));
                    cnt++;
                }
            }
        }
    }

    return finished;
}
bool more_than_4() {
    int cnt = 0;
    for(int i = 0;i < 25;i++) {
        if(flat_board[i]) {
            int r = i / 5;
            int c = i % 5;
            if(map[r][c] == 1) cnt++;
        }
    }
    return cnt >= 4;
}

void dfs(int idx, int cnt) {
    if(cnt == 7) {
        if(more_than_4() && is_adjacent()) {
            answer++;
        }
        return;
    }

    // 조합 생성(중복 불가)
    for(int i = idx;i < 25;i++) {
        if(flat_board[i]) continue;
        flat_board[i] = true;
        dfs(i, cnt + 1);
        flat_board[i] = false;
    }
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    string str;

    // 입력
    for(int i = 0;i < 5;i++) {
        cin >> str;
        for(int j = 0;j < 5;j++) {
            if(str[j] == 'S') map[i][j] = 1;
            else map[i][j] = 2;
        }
    }

    dfs(0,0);
    cout << answer << '\n';
}