문제 출처
1. 문제설명
- 총 25명의 여학생들로 이루어진 반은
5x5
격자 형태로 자리가 배치된다.
- 두 개의 세력이 있다. (
S
, Y
)
- 소문난 칠공주를 결성할수 있는 경우의 수를 구하라
- 규칙
- 7명의 가로 또는 세로로 인접한 여학생들로 구성
- 7명의 학생 중
S
가 우위를 점해야 한다.
- 즉,
S
의 개수가 4개 이상이어야 한다.
2. 알고리즘 설계
- 조합($nCr$)이 조건을 만족하는지 확인하는 문제
- 조합을 뽑기 위해서는 DFS로 하나씩 놓는 방법이 있을 것이다.
- 이 문제는
next_permutation
으로 조합을 구할 수 있다.
N
개의 수열에서 C
개의 조합을 찾는 방법
- 이 문제에서
C
는 7
이 된다.
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. 전체 코드
4. 소감
- 위에 작성한 코드는 나의 오리지널이 아닌 점을 밝힌다.
- 나는 평소 문제를 풀면, 다른 사람의 코드를 보는 습관이 있는데,
- 보통 랭킹이 높은 사람, 그리고 알고리즘 단톡방의 매니저분들의 코드를 참고한다.
- 코드가 굉장히 짧아서 봤더니,
next_permutation
을 활용한 코드였다.
- 해당 함수로
nCr
을 구할 수 있는지 몰랐다…