[백준 22021 / C++] 자동분무기

안녕하세요!

오늘은 백준 플래티넘 4 자동분무기를 풀이하겠습니다.

 

2012년도 정보올림피아드 중등부 4번으로 출제되었는데요,

번뜩이는 수학적 감각이 필요한 재미있는 문제입니다.

 

문제는 아래 링크에서 보실 수 있습니다:

https://www.acmicpc.net/problem/22021

 

Approach 1. Brute-Force & 백트래킹 접근

이 문제를 처음 읽었을 때, 저는 Brute-Force와 백트래킹을 활용한 다음과 같은 풀이를 생각했습니다:

0. 수확량이 저장된 배열 arr[8][8] 에 저장하고, 분무기 위치를 저장할 배열 answer[8][8]을 정의한다.
1. 각 인덱스에서 3가지 상태가 가능하다: (비료, 없음, 제초제). 따라서 배열의 모든 인덱스를, 가능한 경우가 나올 때까지 백트래킹으로 탐색한다.
2. 백트래킹으로 인덱스 (i, j)의 각 경우의 수에 진입하면 arr의 모든 i행, j열에 1을 더하거나 빼거나, 혹은 유지한다.
  2-1. answer[i][j] = ‘제초제 분무기’라면, arr의 i행, j열에 모두 1을 더한다.
  2-2. answer[i][j] = ‘비료액 분무기’라면, arr의 i행, j열에 모두 1을 뺀다.
3. 경우의 수를 돌 때 마다 arr 내의 숫자가 모두 M이 되었는지를 체크한다.

이 접근은 가장 직관적이지만, 유효하지 않습니다.

이는 탐색과 백트래킹의 시간복잡도 때문인데요,
일반적으로 백트래킹은 경우의 수를 따라 트리 형태로, exponential하게 증가하는 모습을 보이기 때문에 주어진 선택지가 아주 작을 때만 (보통 10 이하) 가능합니다.
그렇다면 이 문제의 백트래킹 풀이는 시간복잡도가 어떻게 될까요?
n = 8일 때를 가정하여 단계별로 복잡도를 매겨보겠습니다.

1.   $ n^2 $ : n * n 크기 배열에 입력 
2.  $ 3^{n^2} $ : 각 칸에는 3가지 상태 (비료, 없음, 제초제)가 있어 3의 제곱이다. arr 전체를 돌며 백트래킹을 수행하므로 n*n만큼 제곱한다.
3.  $ n+n $: [0, n) 범위의 자연수 k에 대해 i행, k열 / k행, j열의 모든 값에 접근해 1씩 더하거나 빼고, 분무기 상태를 새로운 배열에 표시.
4.  $ n^2 $: 매번 arr 내의 숫자가 모두 M이 되었는 지를 체크 

 

 

 

 

이렇게 실행한다면, 시간복잡도는 $ O_0 + O_1 * {O_3 + O_2} = n^2 + 3^{n^2} (n^2 + 2n) $ 가 됩니다.
이 말은 즉, n=8일 때 컴퓨터가 연산을 처리하는 데에 소요하는 시간은 약
$ 64 + 3^{64} * (64+64+16) $
정도라는 뜻입니다.
$3^{64}$는 약 $ 3* 10^{30} $ 정도인데요,

컴퓨터는 초당 1억개의 연산을 처리하니 이 방법으로 문제를 풀 경우 문제에 걸린 시간제한을 아득히 넘게 됩니다.
따라서, 백트래킹을 활용한 방법은 유효하지 않습니다.

 

정답 Approach

 

이 문제는 누적합과 수학 지식을 활용해 풀어야합니다.

초기에 모든 칸의 수확량은 M으로 동일합니다.
즉, arr[i][j]의 관점에서, 아직 아무런 것도 뿌리지 않은 밭에서 자신이 속한 행과 열의 모든 칸들의 합은 $ 15 * M $ 입니다.
arr[0][2] 관점에서, 예시를 들어보겠습니다.
arr[0][2]가 속한 행과 열에 속한 칸들은 초록색으로 칠한 부분입니다.

만약 여기서 arr[0][2]와 행도 열도 겹치지 않는 arr[3][4]에 분무기를 두어 파란색 부분에 비료를 뿌린다면, arr[0][2]가 속한 행과 열의 모든 칸들의 합은 $ 15 * M + 2 $ 가 될 것입니다.
마찬가지로, arr[3][4]에 분무기를 두어 파란색 부분에 제초제를 뿌리면, arr[0][2]가 속한 행과 열의 모든 칸들의 합은 $ 15 * M - 2 $ 가 됩니다.

이번에는 arr[0][2]와 행만 겹치는 arr[0][5]에 분무기를 두어 비료를 뿌린 후, arr[0][2]가 속한 행과 열의 모든 칸들의 합을 구해보겠습니다.
arr[0][5]가 속한 행과 열에 속한 칸들은 노란색으로 칠한 부분입니다.

초록색으로 칠한 모든 칸의 수확량 합은 $ 15 * M + 8 $ 입니다.
마찬가지로, arr[0][5]에 분무기를 두어 제초제를 뿌리면, 초록색으로 칠한 모든 칸의 수확량 합은 $ 15 * M - 8 $ 입니다.
이 두 결과는 arr[5][0]에 분무기를 두어도 동일하게 나옵니다.

그렇다면 만약 arr[0][2]에 분무기를 두어 초록색 부분에만 비료를 뿌릴 경우, arr[0][2]가 속한 행과 열의 모든 칸들의 합은 어떻게 될까요?
$ 15 * (M + 1) = 16 * M $ 가 됩니다.

여기서, 저는 다음과 같은 규칙을 발견하였습니다:
arr[i][j]가 속하지 않은 행과 열에서 분무기가 있으면, arr[i][j]가 속한 행과 열의 모든 칸의 합에 2가 감/가산 된다.
arr[i][j]가 속하는 행 또는 열에 분무기가 있으면, arr[i][j]가 속한 행과 열의 모든 칸의 합에 8이 감/가산 된다.
arr[i][j] 위치에 정확히 분무기가 있다면 arr[i][j]가 속한 행과 열의 모든 칸의 합에 15가 감/가산 된다.

이 규칙을 간소화하면
“arr[i][j]에서의 누적합의 홀/짝 상태와 M의 홀/짝 상태가 서로 다르다면, arr[i][j]에 분무기가 존재하는 것이다.” 라는 결론에 도달할 수 있습니다.

 

정리하면 이렇습니다:

임의의 칸 arr[i][j]가 속한 행과 열의 모든 칸들의 합을 2로 나누었을 때 나머지가 M을 2로 나누었을 때와 다르다면,
(i, j)에 분무기가 존재한다.

따라서, 다음과 같이 알고리즘을 짤 수 있습니다:

Function 분무기_찾기():
1. 모든 칸에서 자신이 속한 행과 열의 모든 칸의 누적합을 구해, sum[8][8] 배열에 저장한다.
2. sum[i][j]%2 ≠ M%2라면, i, j 위치에 분무기가 있을 것이다.

이렇게 분무기의 위치는 찾았습니다.

 

그런데 이 분무기에서 살포되는 것이 비료인지 제초제인지는 어떻게 판단할 수 있을까요?

 

문제를 간단화하기 위해 분무기가 비료만 살포한다고 가정해보겠습니다.
앞에서 말했듯이 arr[i][j]에 분무기를 둔다면 sum[i][j]에는 $ 15 * M + 15 $ 가
들어갑니다.
arr[i][j]와 행이나 열을 공유하는 인덱스들은 sum에 $ 15 * M + 8 $ 이,
행이나 열을 모두 공유하지 않는 인덱스들은 sum에 $ 15 * M + 2 $ 가 들어가죠.
근데, 알고보니 분무기에서 나오는 것이 비료가 아니라 제초제였습니다.

이 경우 각 케이스에서 sum 인덱스에 표시한 값과 실제로 sum 인덱스에 들어가있어야 하는 값은 어떻게 달라질까요?

arr[i]j] 자리에 분무기가 있을 때에는 $ 15*M +15 - (15*M -15) = 30 $ ,
arr[i][j]와 행이나 열을 공유하면 $ 15*M + 8 - (15*M - 8 ) = 16 $ ,
arr[i][j]와 행, 열 모두 공유하지 않는다면 $ 15*M + 2 - (15*M - 2) = 4 $

만큼 차이가 납니다.

 

 

규칙을 찾으셨나요?

 

분무기가 있지 않을 때는 값이 4의 배수 단위로 차이가 납니다.

만에 하나 한 칸에 분무기가 2개 있다면 30 * 2로 4의 배수 차이가 날 수도 있지만, 문제 조건 덕에 그럴 일은 없습니다.

즉, 굳이 분무기 여부를 확인하는 단계에서 이게 제초제를 뿜는지 비료를 뿜는지 따질 필요가 없습니다.
분무기가 뭘 뿜든 분무기 여부는 판단할 수 있으니
먼저 분무기 여부를 모두 체크하고,
나중에 그 분무기가 뭘 뿜는지 판단하면 되는 거지요.

그리고 분무기가 뿌리는 것은 다음과 같은 알고리즘으로 판별할 수 있습니다.

Function 분무기_판별():
0. 모든 분무기가 비료를 살포한다고 가정한다.
1. 새 배열 arr_par[8][8]를 만들고, 여기에 모든 분무기가 비료를 뿌린다는 가정 하에 새로운 arr를 구상한다:
  1-1. arr_par[8][8]을 M으로 초기화
  1-2. (i, j)에 분무기가 있다 판단되면 i행과 j열에 모두 1 더한다.
2. (i, j)에 분무기가 있다고 표시되어있고, arr_par[i][j] - arr[i][j] 가 4의 배수가 아닐 때, 그곳에 위치한 분무기는 제초제이다.

최종적으로 “분무기_찾기” 함수와 분무기_판별” 함수를 합치면 됩니다.


정답 코드는 아래의 깃허브를 참조해주시기 바랍니다:

algorithm-study/C++17/백준/Platinum/22021. 자동분무기/자동분무기.cc at dc7d17ecc7876ef21d4e79c36d8c9aefabab0c9a ·