22026번 - 카드 뒤집기 게임 서브태스크언어 제한함수 구현

카드 뒤집기 게임은 혼자서 하는 카드 게임으로, 두 가지 타입의 카드 A, B를 사용한다. 카드 A에는 게임에 적용될 규칙에 관한 정보가 적혀 있다. 구체적으로, 그림 1과 같이 두 정수 $N$ 과 $M(\le N)$, 그리고 $N \times N$ 격자 형태로 문자 'O'와 'X'가 배치된 패턴 $P$가 적혀 있다. 

그림 1

카드 B는 앞면에 문자 'O', 뒷면에 문자 'X'가 적힌 카드다. 카드 B 한 장은 카드 A에 적힌 패턴의 문자 하나를 나타내기 위해 사용될 것인데, 이를 위해 충분히 많은 양의 카드 B가 준비되어 있다.

게임을 시작해보자. 먼저, 카드 A를 하나 선택하고, 그 카드에 적힌 $N$ 값에 따라 $N \times N$ 격자 형태로 카드 B를 배치한다. 처음 배치되는 카드는 모두 'X'가 보이도록 배치해야 한다. 배치된 각 카드는 그림 2처럼 행과 열의 번호로 구분한다.

그림 2

카드의 초기 배치가 끝나면, 플레이어는 아래에 설명하는 '뒤집기'를 필요에 따라 반복한다. 한 번의 '뒤집기'는 두 단계로 구성된다. 

•  단계 1: 카드가 놓인 $N \times N$  격자에서 임의의 한 행 또는 한 열을 선택한다. 또한, 카드 A에 적힌 정수 $M$에 따라 임의의 정수 $k(0 \le k < M)$를 선택한다.
• 단계 2: 단계 1에서 선택한 것이 행 $i$ 라면, $j \equiv k \pmod{M} $인 모든 $j$ 에 대해, 격자 상에서 $(i,j)$ 위치에 있는 모든 카드를 뒤집는다. 유사하게, 단계 1에서 선택한 것이 열 $j$ 라면, $i \equiv k \pmod{M}$인 모든 $i$ 에 대해, 격자 상에서 $(i,j)$ 위치에 있는 모든 카드를 뒤집는다.

플레이어는 '뒤집기'를 반복해서 격자에 놓인 카드의 패턴과 카드 A에 그려진 패턴 $P$를 일치시켜야 한다. 이것이 실제로 가능한 일인지 판별해보자.

여러분은 아래 함수를 구현해야 한다.

bool reversal(int N, int M, vector<string> P)

• 이 함수는 단 한 번만 호출된다.
• 인자로 주어지는 정수 $N$은 격자의 크기를 나타낸다.
• 인자로 주어지는 정수 $M$은 '뒤집기'에서 뒤집는 카드의 간격을 나타낸다.
• 인자로 주어지는 배열 $P$는 길이 $N$인 문자열 $N$개로 구성된 배열이며, $P[i]$는 만들어야 하는 패턴의 $i$번 행을 나타낸다.
• 이 함수는 격자에 놓인 초기 배치로부터 '뒤집기'를 적용하여 패턴 $P$를 만들 수 있으면 true 를 그렇지 않으면 false 를 반환해야 한다.

제출하는 소스 코드의 어느 부분에서도 입출력 함수를 실행해서는 안 된다.

• $1 \le M \le N \le 1\,000$
• $P$에 속한 모든 문자는 'O' 또는 'X' 이다.

$N = 5$, $M = 2$ 이고 패턴 $P =$ [XXXOX, XXXOX, OOOXO, XOXXX, XOXXX] 인 경우를 생각해 보자. 

그레이더는 다음 함수를 호출한다.

reversal(5, 2, [XXXOX, XXXOX, OOOXO, XOXXX, XOXXX])

아래 그림은 초기 상태에서부터 시작하여 `뒤집기'를 할 때, 선택된 행/열 번호와 $k$의 값에 따라 카드의 패턴이 변하는 과정을 보여준다. 이 과정으로 결국 마지막에 패턴 $P$가 만들어진 것을 볼 수 있다. 그러므로, 호출된 reversal 함수는 true를 반환해야 한다.

Sample grader는 아래와 같은 형식으로 입력을 받는다.

• Line $1$: $N$ $M$
• Line $2+i$: $P[i]$

Sample grader는 실제 채점에서 사용하는 그레이더와 다를 수 있음에 유의하라.

• card_public.zip