백준 흰색으로 만들기(17302)

흰색으로 만들기

1. 힌트

1) $3$가지 행동들에 대해서 특징을 파악해봅시다. 최단 횟수일 필요가 없고, 모두 흰색으로 바꿀 수 있는지만 파악하면 됩니다. 또한, 행동의 순서는 상관이 없으므로 맘 편하게 위에서 왼쪽부터 확인해도 됩니다.

2) $2$번 행동과 $3$번 행동은 연관이 깊어 보입니다. $2$번 행동을 한 칸에 나중에 그냥 $3$번 행동을 했다고 치면 그 칸만 반전 시켜 주면 다른 칸에 영향을 주지 않습니다. 반대도 마찬가지입니다.

3) 최단 횟수일 필요가 없으므로 모든 칸에 대해서 $2$번 행동 혹은 $3$번 행동을 해 주고, $2\to3$혹은 $3\to2$로 기존의 행동을 바꿔주면 해당 칸을 반전 시킬 수 있고, 해당 칸 이외에는 영향을 주지 않으므로 언제나 모든 칸을 흰색으로 만들 수 있습니다.

2. 접근

1) 비슷한 문제를 풀어본 적이 있던가?

불 끄기

타일을 껐다 켰다 하는 것이 마치 불 끄기 문제와 유사해보입니다. 불 끄기에서는 맨 윗줄이 정해지면 앞으로 해야 하는 행동이 정해져서 그리디하게 풀어나갈 수 있었지만, 이 문제에서는 맨 윗줄에 대한 행동이 정해지더라도 앞으로 해야 하는 행동이 하나로 딱 정해지지 않습니다. 게다가 $1 \le N, M \le 2000$이기 때문에 맨 윗줄을 $3^{2000}$번 브루트포스로 일일히 시도할 수 없습니다.

2) 순서를 강제할 수 있을까?

어떤 행동을 할 지 $N \times M$개가 정해지면 행동의 순서는 상관이 없으므로 맘 편하게 왼쪽 위부터 확인하는 것으로 합시다.

3) 행동의 특성 확인하기

$2$번 행동과 $3$번 행동은 연관이 깊어 보입니다. $2$번 행동을 한 칸에 나중에 그냥 $3$번 행동을 했다고 칩시다. 그러면 $3$번 행동을 한 것과의 차이는 $S[i][j]$를 한 번 더 반전 시키는 것 밖에 없으므로 $S[i][j]$를 뒤집어줍니다. 이렇게 마음대로 바꾸어버려도 $S[i][j]$에 인접한 칸에 영향을 주지 않습니다. 그렇다면 모든 검은 칸을 언제나 이런 방식으로 바꾸어버릴 수 있습니다!

3. 구현

문제의 특성을 면밀히 파악해야하는 애드 혹스러운 문제입니다.
저는 문제의 크기를 보고 마땅히 적용해야 할 알고리즘이 떠오르지 않으면 문제의 특성을 파악해보고 최대한 쉬운 풀이를 생각해봅니다.

public class Main {
	static int N, M;
	static char[][] S;
	
	static final int[] dy = { -1, 1, 0, 0 };
	static final int[] dx = { 0, 0, -1, 1 };
	
	static boolean inRange(int y, int x) { return 0 <= y && y < N && 0 <= x && x < M; }
	
	static char flip(char c) { return c == 'W' ? 'B' : 'W'; }
	
	static void reverse(int y, int x) {
		S[y][x] = flip(S[y][x]);
		for (int d = 0; d < 4; d++) {
			int ny = y + dy[d]; int nx = x + dx[d];
			if (!inRange(ny, nx)) continue;
			S[ny][nx] = flip(S[ny][nx]);
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder bw = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		S = new char[N][M]; int[][] R = new int[N][M];
		for (int i = 0; i < N; i++) S[i] = br.readLine().toCharArray();
		for (int i = 0; i < N; i++) {
			Arrays.fill(R[i], 3);
			for (int j = 0; j < M; j++) reverse(i, j);
		}
		for (int i = 0; i < N; i++)
			for (int j = 0; j < M; j++)
				if (S[i][j] == 'B') { S[i][j] = 'W'; R[i][j] = 2; }
		bw.append(1).append("\n");
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) bw.append(R[i][j]);
			bw.append("\n");
		}
		System.out.print(bw);
	}

}