문제 출처

1. 문제설명


  • 총 25명의 여학생들로 이루어진 반은 5x5 격자 형태로 자리가 배치된다.
  • 두 개의 세력이 있다. (S, Y)
  • 소문난 칠공주를 결성할수 있는 경우의 수를 구하라
  • 규칙
    • 7명의 가로 또는 세로로 인접한 여학생들로 구성
    • 7명의 학생 중 S가 우위를 점해야 한다.
    • 즉, S의 개수가 4개 이상이어야 한다.



2. 알고리즘 설계


  • 조합($nCr$)이 조건을 만족하는지 확인하는 문제
  • 조합을 뽑기 위해서는 DFS로 하나씩 놓는 방법이 있을 것이다.
  • 이 문제는 next_permutation으로 조합을 구할 수 있다.
  • N개의 수열에서 C개의 조합을 찾는 방법
    • 이 문제에서 C7이 된다.
    • 5x5칸에서 앞 7칸은 false 나머지는 true로 구성된 bool 배열 선언
      • 참고로 배열을 전역으로 선언하면 자동으로 false로 채워진다.
      • fill(mask + 7, mask + SZ * SZ, true);
    • next_permutation을 이용해 조합을 구하는데,
      • false에 해당하는 index가 구성된 조합이다.
    • index의 y, x를 구해 연결되었음을 표시한다.
      • y = index / 5, x = index % 5로 계산할 수 있다.
  • 조건을 만족하는지 체크
    • BFS를 이용해 연결된 지점을 탐색한다.
    • 인접한 곳으로 이동한 횟수가 7이면서, ‘S’의 개수가 4개 이상인지 체크



3. 전체 코드


#include <bits/stdc++.h>
#define Y first
#define X second
using namespace std;
using pii = pair<int, int>;

const int SZ = 5;
const int dy[] = { -1,1,0,0 };
const int dx[] = { 0,0,-1,1 };
string board[SZ];
bool mask[SZ * SZ], vis[SZ][SZ], conn[SZ][SZ];

bool is_correct(pii src) {
	queue<pii> q;
	q.push(src);
	vis[src.Y][src.X] = true;

	int adj = 0, dasom = 0;

	while (!q.empty()) {
		pii cur = q.front();
		q.pop();

		adj++;
		dasom += board[cur.Y][cur.X] == 'S';

		for (int dir = 0; dir < 4; dir++) {
			int ny = cur.Y + dy[dir];
			int nx = cur.X + dx[dir];

			if (ny < 0 || nx < 0 || ny >= SZ || nx >= SZ) continue;
			if (!conn[ny][nx] || vis[ny][nx]) continue;

			q.push({ ny, nx });
			vis[ny][nx] = true;
		}
	}

	return adj == 7 && dasom >= 4;
}

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

	int ans = 0;

	for (int i = 0; i < SZ; i++)
			cin >> board[i];

	fill(mask + 7, mask + SZ * SZ, true);
	do {
		fill_n(&vis[0][0], SZ * SZ, false);
		fill_n(&conn[0][0], SZ * SZ, false);

		pii src = { -1,-1 };

		for (int i = 0; i < SZ * SZ; i++) {
			if (!mask[i]) {
				int y = i / 5;
				int x = i % 5;

				conn[y][x] = true;

				if (src.Y == -1) src = { y,x };
			}
		}
		
		ans += is_correct(src);
	} while (next_permutation(mask, mask + SZ * SZ));

	cout << ans;
	return 0;
}



4. 소감


  • 위에 작성한 코드는 나의 오리지널이 아닌 점을 밝힌다.
  • 나는 평소 문제를 풀면, 다른 사람의 코드를 보는 습관이 있는데,
  • 보통 랭킹이 높은 사람, 그리고 알고리즘 단톡방의 매니저분들의 코드를 참고한다.
    • koosaga님, Yungoon님, 바킹독님
  • 코드가 굉장히 짧아서 봤더니, next_permutation을 활용한 코드였다.
    • 해당 함수로 nCr을 구할 수 있는지 몰랐다…