시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB158758.333%

문제

대학생 선우는 건축가 제이크한테 감리 실습을 받고 있다. 선우가 현장에서 건물을 시찰해서 설계도를 그리면 제이크가 설계도를 잘 그렸는지 확인한다. 설계도는 가로 $M$픽셀, 세로 $N$픽셀 크기의 흑백 그림이다.

선우와 제이크는 예상치 못한 문제에 직면했다. 선우가 설계도를 복사해서 제이크에게 줄 때 설계도에 쌓인 먼지도 같이 복사되어서 제이크가 설계도를 알아볼 수 없게 되었다. 선우가 빈 종이를 여러 번 복사하면서 확인해본 결과 양옆 또는 위아래로 인접한 두 픽셀에 동시에 먼지가 쌓이지 않는다는 것을 깨달았다.

선우는 먼지의 성질을 적절히 활용하면 제이크가 원래 설계도를 다시 복원할 수 있을 거라고 생각한다. 선우는 설계도를 복사하기 전에 손가락을 이용하여 한 행 또는 열에 있는 모든 먼지를 제거할 수 있다. 먼지는 금방 다시 쌓이기 때문에 선우는 먼지를 $C$회 이하로 쓸어서 설계도를 복원할 수 있게 하려고 한다. 선우와 제이크를 도와 설계도를 복원하는 프로그램을 작성하여라.

함수 목록 및 정의

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

int[] wipe_dust(int subtask, int[][] B)
  • $subtask$: 서브태스크 번호.
  • $B$: $N \times M$ 크기 배열. 도면의 $i+1$행 $j+1$열 픽셀이 검은색이면 $B[i][j] = 1$, 그렇지 않으면 $B[i][j] = 0$이다.
  • 이 함수는 크기가 $0$ 이상 $min(C, N+M)$ 이하인 배열 $W$를 반환해야 한다. 선우가 $i$($1 \leq i \leq N$)행을 문지르고 도면을 복사한다면 $W$의 원소로 $i$가 있어야 하며, 선우가 $j$($1 \leq j \leq M$)열을 문지르고 도면을 복사한다면 $W$의 원소로 $-j$가 있어야 한다. $W$에는 같은 값이 중복되면 안 된다.
int[][] restore_blueprint(int subtask, int[][] X)
  • $subtask$: 서브태스크 번호.
  • $X$: $N \times M$ 크기 배열. 먼지와 함께 복사된 도면의 $i+1$행 $j+1$열 픽셀이 검은색이면 $X[i][j] = 1$, 그렇지 않으면 $X[i][j] = 0$이다.
  • 이 함수는 먼지를 제거한 원래 도면 $B'$를 반환해야 한다.

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

여러분의 프로그램은 두 번 실행된다. 첫 번째 실행에서는 wipe_dust 함수만 호출하며 두 번째 실행에서는 restore_blueprint 함수만 호출한다. 프로그램의 실행 시간은 두 번의 실행 시간을 합한 값이며 메모리 사용량은 두 번의 사용 메모리 중 최댓값으로 계산된다.

제한

모든 데이터에 대해서, $3 \leq N, M \leq 1\,000$ 을 만족한다.

서브태스크 1 (1점)

  • 도면 $B$의 모양은 십자가 모양이다. 즉, 정수 $H \geq 1$, $V \geq 1$, $V \leq R < N-V$, $H \leq C < M-H$가 존재하여 $B[r][c] = 1$일 필요충분조건이 $(r, c) \in$ $\left \{ (R, C+i) | -H \leq i \leq H \right \}$ $\bigcup$ $\left \{ (R+i, C) | -V \leq i \leq V \right \}$이어야 한다.
  • $C = 4$

서브태스크 2 (1점)

  • 도면 $B$의 모양은 왼쪽 위의 점이 직각인 직각삼각형 모양이다. 즉, 정수 $L \geq 2$, $0 \leq R < N-L$, $0 \leq C < M-L$가 존재하여 $B[r][c] = 1$일 필요충분조건이 $(r, c) \in$ $\left \{ (R, C+i) | 0 \leq i \leq L \right \}$ $\bigcup$ $\left \{ (R+i, C) | 0 \leq i \leq L \right \}$ $\bigcup$ $\left \{ (R+i, C+L-i) | 0 \leq i \leq L \right \}$이어야 한다.
  • $C = 2$

서브태스크 3 (1점)

  • 도면 $B$의 모양은 $1$개 이상의 $3$행 $2$열 직사각형이 서로 겹치지 않도록 배치된 모양이다. 즉, 공집합이 아닌 집합 $S \subseteq$ $\left \{ (r, c) | 0 \leq r < N, 0 \leq c < M \right \}$이 존재하여 모든 $(r_1, c_1)$, $(r_2, c_2)$ $\in S$에 대하여 $(r_1, c_1) \neq (r_2, c_2)$과 $\left | r_1 - r_2 \right | \geq 3$ or $\left | c_1 - c_2 \right | \geq 2$를 만족하고 $B[r][c] = 1$일 필요충분조건이 $(r, c) \in$ $\left \{ (r, c) | \exists (i, j) \in S \text{ s.t. } i \leq r \leq i+2, j \leq c \leq j+1 \right \}$이어야 한다.
  • $C = 1$

예제 1

위 왼쪽 그림과 같이 도면 [[0, 1, 0, 0], [1, 1, 1, 0], [0, 1, 0, 0]] 을 복사하는 경우를 생각해보자. 그레이더는 wipe_dust(1, [[0, 1, 0, 0], [1, 1, 1, 0], [0, 1, 0, 0]])를 호출한다.

여러분이 [2]를 반환했다면 이는 선우가 $2$행을 문지르고 도면을 복사했다는 것을 의미한다. 이후 도면에 먼지가 일부 달라붙은 상태로 복사되면 위 오른쪽 그림과 같이 복사된다.

그레이더는 restore_blueprint(1, [[1, 1, 1, 0], [1, 1, 1, 1], [1, 1, 1, 0]])을 호출한다.

여러분은 restore_blueprint 함수에서 [[0, 1, 0, 0], [1, 1, 1, 0], [0, 1, 0, 0]]를 반환해야 한다.

샘플 그레이더

샘플 그레이더는 첫 번째 줄에 $subtask, N, M$을 입력받는다. 두 번째 줄부터 $N$개의 줄에는 도면의 정보 $B[i][j]$에 해당하는 $M$개의 정수를 사이 공백 없이 입력받는다.

다음 줄부터 $N$개의 줄에는 먼지의 정보 $D[i][j]$에 해당하는 $M$개의 정수를 사이 공백 없이 입력받는다. $i+1$행 $j+1$열에 도면에 먼지가 쌓인다면 $D[i][j] = 1$이고 그렇지 않다면 $D[i][j] = 0$이다.

샘플 그레이더는 wipe_dust 함수와 restore_blueprint 함수를 한 번씩 호출하며, 도면의 성공적인 복원 여부(Correct 또는 Wrong)를 출력한다.

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

출처

Contest > BOJ User Contest > FunctionCup > FunctionCup 2023 WX번

제출할 수 있는 언어

C++17, C++20, C++17 (Clang), C++20 (Clang)

채점 및 기타 정보

  • 예제는 채점하지 않는다.