[BOJ] C++ 1941: 소문난 칠공주 - BFS와 백트래킹 섞어 쓰기

1941번: 소문난 칠공주

예제

YYYYY
SYSYS
YYYYY
YSYYS
YYYYY

ans : 2

---

처음에는 일반적인 백트래킹으로 접근했다. 어차피 데이터의 크기가 25로 매우 작고 시간은 2초로 여유롭니 모든 점을 시작점으로 두고 O(25) 재귀식을 상하좌우 중 방문할 수 있다면 방문하는 식으로 짜서 백트래킹으로 구현하였다. 이 방법에서 두 가지 문제점을 발견했는데, 사진으로 보는 게 나을 것 같다.

애초에 백트래킹은 재귀식으로 해야한다는 고정관념에 잘못 접근한 것 같다.

차라리 데이터가 매우 작으므로 모든 공주가 될 수 있는 조합을 구해서 그 조합이 조건을 만족하는지 판단하는 방법으로 접근했다. 조합을 구하는 방법이 7중 for문밖에 떠오르지 않아서 찾아보니 next_permutation()이라는 함수를 발견했다.

---

next_permutation 함수는 <algorithm> 헤더에 포함되어 있고, 순열을 생성하는 데 사용된다. 이 함수는 현재 순열을 다음 순열로 변경하고, 변경된 순열이 존재하면 true를, 그렇지 않으면 false를 반환한다. 예를 들어 {1, 2, 3} 배열에 next_permutation을 적용하면서 출력하면 아래와 같다.

#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    std::vector<int> numbers = {1, 2, 3};


    do {
        for (int num : numbers) {
            std::cout << num << ' ';
        }
        std::cout << '\n';
    } while (std::next_permutation(numbers.begin(), numbers.end()));

    return 0;
}

출력은 아래와 같다.

1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 1 2 
3 2 1

이 함수를 사용할 때 굉장히 중요한 주의점이 있는데 순열을 생성할 배열이 정렬되어있어야 한다는 것이다.

// 초기설정 [0,0] ~ [1,0]을 공주로 선택하고 시작한다.
// next_permutation 함수는 정렬된 배열에 한해서만 작동하기에 false가 앞에 나와야 한다. 따라서 선택한 공주는 false로 표시한다.
fill(princess + 7, princess + 25, true);

do
{
    bfs();

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

실제 구현을 위와같이 하였는데, 처음에는 0~7을 true로 초기화하고 그 뒤를 false로 초기화했다가 next_permutation이 작동하지 않아서 한참 고생했다. bfs()는 bfs 정석대로 구현해 주면 된다. 다만, 다음 원소 방문 조건에 그 원소가 공주에 포함되었는지 빠뜨리면 안 되고, 도연파의 수를 세면서 4 이상이면 바로 종료해 주면서 백트래킹을 사용해 줄 수 있었다.

/** BackTracking 1941 소문난 칠공주 **/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;
string stu[5];
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};
bool princess[25];
int res = 0;

void bfs()
{
    queue<pair<int, int>> Q;
    bool visited[5][5];
    for (int i = 0; i < 5; i++)
        for (int j = 0; j < 5; j++)
            visited[i][j] = false;

    int doyeon_num = 0, cnt = 0;
    for (int i = 0; i < 25; i++)
    {
        if (!princess[i])
        {
            // 처음으로 방문한 공주를 시작으로 bfs 시작
            int x = i / 5;
            int y = i % 5;
            visited[x][y] = true;
            Q.push({x, y});
            while (!Q.empty())
            {
                auto cur = Q.front();
                Q.pop();
                cnt++;
                if (stu[cur.first][cur.second] == 'Y')
                    doyeon_num++;
                if (doyeon_num >= 4)
                    break;
                for (int dir = 0; dir < 4; dir++)
                {
                    int nx = cur.first + dx[dir];
                    int ny = cur.second + dy[dir];
                    if (nx < 0 || ny < 0 || nx > 4 || ny > 4)
                        continue;
                    if (visited[nx][ny])
                        continue;
                    if (princess[nx * 5 + ny])
                        continue;
                    visited[nx][ny] = true;
                    Q.push({nx, ny});
                }
            }
            if (cnt != 7 || doyeon_num >= 4)
                // cnt는 한 번의 bfs로 센 공주의 수이다. 7이 아니라면 공주들이 인접한게 아니다.
                return;
            res++;
            return;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    for (int i = 0; i < 5; i++)
        cin >> stu[i];

    // 초기설정 [0,0] ~ [1,0]을 공주로 선택하고 시작한다.
    // next_permutation 함수는 정렬된 배열에 한해서만 작동하기에 false가 앞에 나와야 한다. 따라서 선택한 공주는 false로 표시한다.
    fill(princess + 7, princess + 25, true);

    do
    {
        bfs();

    } while (next_permutation(princess, princess + 25));
    cout << res;
}