백준 22021 <자동분무기> Python

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

---

해당 문제는 크게 두 부분으로 나누어 생각할 수 있습니다.

종류에 상관없이 분무기의 위치를 알아내는 부분 / 위치를 알아낸 뒤 종류를 파악하는 부분

 

우선 분무기의 위치를 알아내는 부분은 생각하기 쉽습니다.

어느 부분에 분무기가 존재한다고 가정하겠습니다.

분무기는 십자 형태로 내용물을 살포할텐데, 살포되는 칸의 수는 15칸이 됩니다.

그렇다면 자연스럽게 특정 위치에서 자신의 십자범위로 더해지거나 빼진 값의 합을 구하면 홀수가 나오게 됩니다.

다른 위치에서의 분무기가 영향을 줄 수 있다고 생각할 수 있는데, 어느 위치에 다른 분무기가 존재하던 십자합에는 짝수만큼의 영향을 주므로 특정 위치의 더해지거나 빼진 값들의 십자합이 홀수라면 해당 위치는 종류에 상관없이 분무기가 위치하게 됩니다.

주어지는 데이터에서 기본값을 뺀 값들로 맵을 새로 구성하면 특정 인덱스에서 순수하게 더해지고 빼진 값들이 나오게 되는데

여기서 십자합을 구한 뒤 짝수 / 홀수 구분을 해주면 분무기의 위치를 알 수 있습니다.

---

이제 분무기의 위치를 파악했으니 그 종류를 파악해야 합니다.

우리는 여기서 모든 분무기가 비료분무기라고 가정하겠습니다.

그 뒤에 새로 맵을 구성한 뒤 원래 맵과의 차이를 구해줍니다. 그렇다면 가정한 값과의 차이를 알 수 있습니다.

그리고 원래 맵과의 차이를 기록한 맵에서 다시 특정 위치에서 더해지거나 빼진 값들의 십자합을 구할텐데, 이번에는 우리가 구한 분무기의 위치에서만 구해주면 됩니다.

 

우리의 십자합에 영향을 주는 것은

( 자신이 제초분무기일 경우 / 다른 위치에 있는 분무기가 제초분무기일 경우)

밖에 없습니다.

 

그 중 자신이 제초분무기일 경우를 살펴보면

자신이 영향을 주는 칸은 자신의 십자위치 15칸 x 2(=1 -(-1)),

다른 위치에 있는 제초분무기가 영향을 주는 칸의 수 x 2(=1- (-1))

인데 다른 위치에 있는 제초분무기는 하나당 십자합의 범위에 있는 칸 중 두 칸 혹은 여덟칸에 영향을 주므로 결과적으로 30 + (2 or 8)x2 의 차이가 발생합니다.

 

자신이 제초분무기가 아닐 경우 자신의 십자위치는 영향을 주지 않으므로 

다른 위치에 있는 제초분무기가 영향을 주는 칸의 수 x 2(=1- (-1))

인데 다른 위치에 있는 제초분무기는 하나당 십자합의 범위에 있는 칸 중 두 칸 혹은 여덟칸에 영향을 주므로 결과적으로 (2 or 8)x2 의 차이가 발생합니다.

 

여기서, 30은 4의 배수가 아니므로 위의 각 값을 4 로 나누었을 때 4의 배수인지 아닌지를 판단하면 분무기의 종류를 파악할 수 있습니다.

 

---

import sys

input = sys.stdin.readline

def solution(M, data_map):

    # 기본값씩 빼기

    for i in range(len(data_map)):

        data_map[i] = list(map(lambda x: x-M, data_map[i]))

    # 인덱스마다 십자합

    sum_map = [[0 for _ in range(8)] for __ in range(8)]

    for i in range(8):

        sum_row = sum(data_map[i])

        for j in range(8):

            sum_column = sum([data_map[ii][j] for ii in range(8)])

            sum_map[i][j] = sum_row + sum_column - data_map[i][j]

    # 분무기의 위치

    target_idxs = [[i, j] for j in range(8) for i in range(8) if sum_map[i][j]%2]

    # 모두 비료분무기라고 가정하고 맵을 재구성

    all_pos_map = [[30 for _ in range(8)] for __ in range(8)]

    for x, y in target_idxs:

        for i in range(8):

            for j in range(8):

                if i == x or j == y:

                    all_pos_map[i][j] += 1

   

    # 실제 맵과 가정한 맵의 차이

    for i in range(8):

        for j in range(8):

            all_pos_map[i][j] -= data_map[i][j] + 30

   

    # 타겟 인덱스마다 십자합

    all_sum_map = [[0 for _ in range(8)] for __ in range(8)]

    for i in range(8):

        sum_row = sum(all_pos_map[i])

        for j in range(8):

            sum_column = sum([all_pos_map[ii][j] for ii in range(8)])

            all_sum_map[i][j] = sum_row + sum_column - all_pos_map[i][j]

    symbols = ['-' if all_sum_map[i][j]%4 else '+' for i, j in target_idxs]

   

    symbol_map = [['.' for _ in range(8)] for __ in range(8)]

    for [i, j], symbol in zip(target_idxs, symbols):

        symbol_map[i][j] = symbol

   

    for i in range(8):

        print(*symbol_map[i])

# 입력

M = int(input().strip())

data_map = [list(map(int, input().strip().split())) for _ in range(8)]

solution(M, data_map)