[C++] Boj 1941 소문난 칠공주
문제 링크
접근
문제를 풀다가 어떻게 풀어야 할지 긴가민가해서 알고리즘 분류 항목을 열어 훔쳐보았다...
열심히 생각해 본 결과는 아래와 같다.
- 25C7을 구한다.
- 7명이 접해 있는지 확인한다.
- 7명이 접해 있다면, 이다솜파의 수가 4 이상일 때, ans를 카운트한다.
하지만 구현에는 실패하였다. 바킹독 님의 답안에는 next_permutation를 사용한 풀이가 있었지만, 나는 next_permutation에 대한 이해가 부족했다.
next_permutation에 대한 공부를 더 하고 이 문제를 이해해 보려 한다.
전체 코드
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
// 1. 25C7을 구함.
// 2. 7명이 접해있는지 확인
// 3. 이다솜파의 수 확인
// 공부해야 할 것
// 1. next_permutation 정확한 이해
// 2. 문제 답에 대한 정확한 이해
string board[5];
int ans;
// next_permutation
bool mask[25];
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { -1, 1, 0, 0 };
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
for (int i = 0; i < 5; i++)
{
string str;
cin >> str;
board[i] = str;
}
// 25개 중 7개를 뽑으므로,
// mask 배열을 0 7개, 나머지는 1로 채운다.
fill(mask + 7, mask + 25, true);
do
{
queue<pair<int, int>> q;
int dasom = 0, cnt = 0;
bool Is7[5][5] = {}, visited[5][5] = {};
for (int i = 0; i < 25; i++)
{
if (mask[i] == 0)
{
int x = i / 5;
int y = i % 5;
Is7[x][y] = true;
if (q.empty())
{
q.push({ x, y });
visited[x][y] = true;
}
}
}
while (!q.empty())
{
int x = q.front().first;
int y = q.front().second;
q.pop();
cnt++;
dasom += board[x][y] == 'S';
for (int k = 0; k < 4; k++)
{
int nx = x + dx[k];
int ny = y + dy[k];
if (nx < 0 || nx >= 5 || ny < 0 || ny >= 5) continue;
if (visited[nx][ny] || !Is7[nx][ny]) continue;
q.push({ nx, ny });
visited[nx][ny] = true;
}
}
ans += (cnt >= 7 && dasom >= 4);
} while (next_permutation(mask, mask + 25));
cout << ans;
return 0;
}
분석
do
{
queue<pair<int, int>> q;
int dasom = 0, cnt = 0;
bool Is7[5][5] = {}, visited[5][5] = {};
.
.
.
} while (next_permutation(mask, mask + 25));
전체 틀은 25C7을 구하는 next_permutation을 이용한 do-while문이다.
7명이 인접해 있는지 확인할 때 bfs를 사용하므로, q를 선언하였다.
visited 배열은 bfs 탐색 시 사용한다.
Is7 배열은 7명 각각의 좌표를 표시하기 위해 사용한다.
for (int i = 0; i < 25; i++)
{
if (mask[i] == 0)
{
int x = i / 5;
int y = i % 5;
Is7[x][y] = true;
if (q.empty())
{
q.push({ x, y });
visited[x][y] = true;
}
}
}
next_permutation의 mask 배열을 0이 7개, 1이 나머지로 구성하였으므로 mask[i]가 0일 때, 그 수를 뽑아 준다.
이때 mask 배열은 1차원 배열로 선언하였으므로
int x = i / 5;
int y = i % 5;
와 같은 방법으로 2차원 배열의 좌표로 변환한다.
다음, 7명 배열에 좌표를 기록하고, q가 비어있으면 q에 push한다.
이것을 i==25까지 반복하면 Is7 배열은 7개가 true로 설정되어 있고, q에는 Is7의 최초 좌표만이 들어 있을 것이다.
while (!q.empty())
{
int x = q.front().first;
int y = q.front().second;
q.pop();
cnt++;
dasom += board[x][y] == 'S';
for (int k = 0; k < 4; k++)
{
int nx = x + dx[k];
int ny = y + dy[k];
if (nx < 0 || nx >= 5 || ny < 0 || ny >= 5) continue;
if (visited[nx][ny] || !Is7[nx][ny]) continue;
q.push({ nx, ny });
visited[nx][ny] = true;
}
}
ans += (cnt >= 7 && dasom >= 4);
이제 bfs 탐색을 한다.
탐색을 할 때마다 인접해 있는 인원 수를 카운팅 해 주며, 그 사람이 이다솜파일 경우 따로 카운팅 해 준다.
다른 그래프 탐색 문제와 비슷하게 4방향으로 탐색해 준다.
이미 방문한 좌표거나, 그 좌표에 있는 사람이 Is7 배열에 속한 7명 중 한 사람이 아니라면 continue한다.
이렇게 하면 오로지 최초로 탐색된 인접한 사람만이 q에 들어갈 수 있는 것이다.
7명 중, 이 좌표와 4방향으로 인접한 사람이 없는 경우에는 q에 push된 게 없으므로 while문은 종료된다.
마지막으로 인접한 사람이 7명(이상)이며 이다솜파가 4명 이상일 경우 ans에 카운팅 한다.
