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

www.acmicpc.net/problem/1941

1941번: 소문난 칠공주

새롭게 알게된 점

십자가 모양은 일반적인 DFS + 백트래킹으로 문제를 해결할 수 없다.

DFS와 BFS를 같이 쓰는 문제가 존재한다. (이번 문제가 그러했음)

 

문제를 해결하는 순서는 다음과 같습니다.

1. 학생 25명중 7명을 선택하는 조합을 DFS를 통해 구하기

2. 해당 조합에서 다솜이파 학생이 4명 이상인지 확인하는 isMoreThanFour() 함수 구현

3. 해당 조합에서 선택된 학생이 인접한지 확인하는 isAdjacent() 함수 구현

4. 2번 3번을 모두 만족하는 조합이라면 answer++

 

선택된 학생이 인접한지 확인하는 것은 BFS를 사용했습니다. 포인트는 큐가 선택된 학생에 한해서만 탐색하기 위해 checked 배열에 선택된 학생의 위치를 체크하는 것입니다. 

 

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

char map[5][5];
bool pick[25];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int answer;

// 다솜이파 학생이 4명 이상인지 확인
bool isMoreThanFour() {
    int sum = 0;
    for(int i = 0; i < 25; i++) {
        // 행 인덱스 : 학생 번호 / 5, 열 인덱스 : 학생 번호 % 5
        // 다솜이파 학생인 경우 sum++
        if(pick[i] && map[i / 5][i % 5] == 'S') sum++;
    }
    if(sum >= 4) return true;
    else return false;
}

// 학생들끼리 인접한 조합인지 확인
bool isAdjacent() {
    queue<pair<int, int > > q;
    bool visit[5][5]; // 방문 여부 체크
    bool checked[5][5]; // 이전에 선택된건지 체크
    
    // 초기화
    memset(visit, false, sizeof(visit));
    memset(checked, false, sizeof(checked));
    
    bool first = true;
    for(int i = 0; i < 25; i++) {
        if(pick[i]) {
            // 선택된 학생만 큐를 돌기 위해 checked 배열에 미리 체크
            checked[i / 5][i % 5] = true;
            // 처음 선택된 학생만 큐에 넣어줌 (큐의 시작점)
            if(first) {
                first = false;
                q.push({i / 5, i % 5});
                visit[i / 5][i % 5] = true;
            }
        }
    }
    
    // 첫 학생은 큐에 들어갔으므로 cnt는 1부터 시작
    int cnt = 1;
    while(!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        // 모든 조건을 만족하고 학생이 7명이면 true 리턴
        if(cnt == 7) return true;
        
        for(int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            // 범위를 벗어나는 경우 continue
            if(nx < 0 || nx >= 5 || ny < 0 || ny >= 5) continue;
            // 전에 방문했거나, 선택된 학생이 아니라면 continue; 
            if(visit[nx][ny] || !checked[nx][ny]) continue;
            q.push({nx, ny});
            visit[nx][ny] = true;
            cnt++;
        }
    }
    
    // 위의 조건에 하나라도 위반되면 큐가 전부 pop되고 난 후 
    // while문을 빠져나왔을 때, 7명이 안되므로 false를 리턴
    return false;
}

// DFS : 25명의 학생 중 7명을 선택하는 조합 
void DFS(int idx, int cnt) {
    if(cnt == 7) {
        if(isMoreThanFour() && isAdjacent()) answer++;
        return;
    } else {
        for(int i = idx; i < 25; i++) {
            if(!pick[i]) {
                pick[i] = true;
                DFS(i, cnt + 1);
                pick[i] = false;
            }
        }
    }
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    for(int i = 0; i < 5; i++) {
        for(int j = 0; j < 5; j++) {
            cin>>map[i][j];
        }
    }
    
    DFS(0, 0); // 인덱스 번호, 선택된 학생 수
    cout<<answer;
}