[백준/17302] 흰색으로 만들기 (Python)

Problem : https://www.acmicpc.net/problem/17302

17302번: 흰색으로 만들기

 

Difficulty : Gold 1

 

Status : Solved

 

Time : 00:46:53

 

---

 

문제 설명

 

N행 M열 격자판의 각 격자가 흰색 또는 검은색으로 칠해져 있다. 각 칸에 대해 다음의 3가지 중 1가지 행동을 취할 수 있다.

1. 아무 변화도 주지 않는다.
2. 선택한 칸과 인접한 모든 칸의 색을 반전시킨다. 단, 선택한 칸은 반전시키지 않는다.
3. 선택한 칸 및 그 칸과 인접한 모든 칸의 색을 반전시킨다.

 

당신은 모든 칸을 흰색으로 만들고자 한다. 모든 칸을 흰색으로 만드는 방법을 구하여라.

 

입력 및 출력

 

입력

 

첫 줄에 N과 M이 주어진다. (1 ≤ N, M ≤ 2,000)

다음 줄부터 N개의 줄에 걸쳐 각 행의 상태를 나타내는 길이 M의 문자열이 주어진다. 모든 문자열은 'B'와 'W'로 이루어져 있다. i 번째 줄, j 번째 문자가 'B'일 경우 해당 칸이 검은색이며 'W'일 경우 해당 칸이 흰색임을 의미한다.

 

출력

 

만약 모든 칸을 흰색으로 만드는 것이 불가능하다면 첫 줄에 -1을 출력한다.

가능하다면 첫 줄에 1을 출력하고, 다음 줄부터 N개의 줄에 걸쳐 M개의 수를 공백 없이 출력한다.

i 번째 줄의 j 번째 수는 i 번째 줄, j 번째 칸에 취한 행동을 나타낸다. 1은 아무런 변화를 주지 않은 것, 2는 인접한 모든 칸을 반전시킨 것, 3은 그 칸 및 인접한 모든 칸을 반전시킨 것을 의미한다.

만약 가능한 답이 여럿이라면 그 중 아무것이나 출력한다.

 

입력 예시

 

2 3
WBW
BWB

 

출력 예시

 

1
111
121

 

 

---

 

풀이

 

첫 번째 예제에 파닥파닥 낚였다...

 

언뜻 보면 이 문제와 비슷해 보인다.

 

2023.06.04 - [알고리즘 문제/백준] - [백준/2138] 전구와 스위치 (Python)

[백준/2138] 전구와 스위치 (Python)

 

하지만 그리디하게 풀기에는 N, M의 크기가 매우 크며(초기 상태를 정하는 데만 해도 3^2000까지 소요될 수 있다) 이후의 경우의 수도 하나가 아닌 여러 케이스가 존재할 수 있다.

 

여기서 발상을 전환해 보자. 2번과 3번은 '그 지점의 흑백을 전환하는 여부'가 차이가 있다. 즉 2번을 3번으로, 혹은 3번을 2번으로 전환함으로써 그 지점의 흑백만을 전환할 수 있다. 따라서 모든 칸을 2번 규칙에 따라 뒤집어 준 후, 이후 'B'에 해당하는 칸만 3번으로 전환한다면 O(NM)의 시간 내에 풀이 가능하다!

 

조건에 대한 관찰력을 요하는 문제였다... 무섭다.

 

풀이 코드

import sys
input = sys.stdin.readline
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

N, M = map(int, input().split())
map_list = [list(input().strip()) for _ in range(N)]
answer = [['2']*M for _ in range(N)]

def reverse(x, y) :
  for k in range(4) :
    ax, ay = x + dx[k], y + dy[k]
    if -1 < ax < M and -1 < ay < N :
      map_list[ay][ax] = 'B' if map_list[ay][ax] == 'W' else 'W'

for i in range(N) :
  for j in range(M) :
    reverse(j, i)

for i in range(N) :
  for j in range(M) :
    if map_list[i][j] == 'B' :
      answer[i][j] = '3'

print(1)
for _answer in answer :
  print(''.join(_answer))

풀이 완료!