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

📌 문제

BOJ 바로가기

주어지는 조건에 맞에 소문난 칠공주를 구성해야 한다. 공주들의 자리는 서로 인접해야 하고, 이다솜파가 4명 이상으로 구성되어야 한다.

🗡 풀이

처음엔 DFS로 풀었는데, 이렇게 풀면 틀린다. 칠공주의 자리가 십자가 모양으로 되어있는 경우는 DFS로 탐색할 수가 없기 때문이다. 그래서 코드를 갈아엎었다.

📍 비트마스크를 이용해 7명이 선택되는 모든 경우의 수를 구한다. 모든 경우의 수는 다음 반복문을 이용해 구할 수 있다.
for (int s = 0; s < (1 << 25); s++)

이렇게 선택된 공주의 자리 정보를 princess 벡터에 담는다. 24번 공주의 경우 { 24 / 5, 24 % 5 }, 즉 {4, 4}로 표기한다.

📍 선택된 공주들 중 다솜파가 몇 명인지 카운트한다.

📍 map 배열의 복사본 temp배열을 만들고, 선택한 공주의 자리 값을 P로 바꿔준다. 이후 BFS를 진행한다.

📍 방문하지 않는 공주의 자리가 있는지, 다솜파가 4명 이상인지 체크한다. 조건을 만족할 경우 ans의 값을 1 늘린다.

🚩 정답 소스코드

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

char map[5][5], temp[5][5];
int ans = 0;
bool visited[5][5] = { false };
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };

void bfs(int x, int y) {
	queue<pair<int, int>> q;
	memset(visited, false, sizeof(visited));
	q.push({ x, y });
	visited[x][y] = true;
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (0 <= nx && nx < 5 && 0 <= ny && ny < 5 && !visited[nx][ny] && temp[nx][ny] == 'P') {
				q.push({ nx, ny });
				visited[nx][ny] = true;
			}
		}
	}
}

int main() {
	for (int i = 0; i < 5; i++)
		for (int j = 0; j < 5; j++)
			cin >> map[i][j];
	for (int s = 0; s < (1 << 25); s++) {
		int cnt = 0;
		for (int i = 0; i < 25; i++) {
			if (s & (1 << i))
				cnt++;
		}
		if (cnt == 7) {
			// 임시지도에 map 복사
			for (int i = 0; i < 5; i++)
				for (int j = 0; j < 5; j++)
					temp[i][j] = map[i][j];
			// princess벡터에 공주 정보 담기, 임시지도의 공주 자리에 P 표시, 다솜파가 네명 이상인지 체크
			vector<pair<int, int>> princess;
			int dasom = 0;
			for (int i = 0; i < 25; i++) {
				if (s & (1 << i)) {
					princess.push_back({ i / 5, i % 5 });
					if (map[i / 5][i % 5] == 'S') dasom++;
					temp[i / 5][i % 5] = 'P';
				}
			}
			// 공주들의 자리가 인접해 있는지 체크
			bfs(princess[0].first, princess[0].second);
			bool check = true;
			for (int i = 0; i < 7; i++) {
				if (!visited[princess[i].first][princess[i].second]) {
					check = false;
					break;
				}
			}
			if (check && dasom >= 4)
				ans++;
		}
	}
	cout << ans;
	return 0;
}