BOJ_17302_흰색으로 만들기 (Java, C++)

[Gold I] 흰색으로 만들기 - 17302

문제 링크

성능 요약

메모리: 44860 KB, 시간: 668 ms

분류

애드 혹

제출 일자

2025년 1월 24일 21:23:54

문제 설명

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은 그 칸 및 인접한 모든 칸을 반전시킨 것을 의미한다.

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

문제 풀이

코드

Java 코드

package BOJ_17302_흰색으로만들기;
        
/**
 * Author: nowalex322, Kim HyeonJae
 */

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static int N, M;
    static char[][] board;
    static int[] dr = {-1, 1, 0, 0}, dc = {0, 0, -1, 1};
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
//        br = new BufferedReader(new InputStreamReader(System.in));
        br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_17302_흰색으로만들기/input.txt")));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        board = new char[N][M];
        for (int i = 0; i < N; i++) {
            String str = br.readLine();
            for (int j = 0; j < M; j++) {
                board[i][j] = str.charAt(j);
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                for(int k=0; k<4; k++) {
                    int nr = i + dr[k];
                    int nc = j + dc[k];
                    if(isValid(nr, nc)) command2(nr, nc);
                }
            }
        }

        sb.append(1).append("\n");

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if(board[i][j] == 'B') sb.append(3);
                else sb.append(2);
            }
            sb.append("\n");
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }

    private void command2(int r, int c) {
        if(board[r][c] == 'W') board[r][c] = 'B';
        else board[r][c] = 'W';
    }

    private boolean isValid(int r, int c) {
        return r >= 0 && r < N && c >= 0 && c < M;
    }
}

---

C++ 코드

/**
 * Author: nowalex322, Kim HyeonJae
 */
#include <bits/stdc++.h>
using namespace std;

// #define int long long
#define MOD 1000000007
#define INF LLONG_MAX
#define ALL(v) v.begin(), v.end()

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

int N, M;
vector<vector<char>> board;
int dr[4] = {-1, 1, 0, 0}, dc[4] = {0, 0, -1, 1};

bool isValid(int r, int c) { return r >= 0 && r < N && c >= 0 && c < M; }

void command2(int r, int c) { board[r][c] = (board[r][c] == 'W') ? 'B' : 'W'; }

void solve() {
    cin >> N >> M;

    board.resize(N, vector<char>(M));

    for (int i = 0; i < N; i++) {
        string str;
        cin >> str;
        for (int j = 0; j < M; j++) {
            board[i][j] = str[j];
        }
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            for (int k = 0; k < 4; k++) {
                int nr = i + dr[k];
                int nc = j + dc[k];
                if (isValid(nr, nc)) command2(nr, nc);
            }
        }
    }

    cout << 1 << "\n";
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cout << (board[i][j] == 'B' ? 3 : 2);
        }
        cout << "\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int tt = 1;  // 기본적으로 1번의 테스트 케이스를 처리
    // cin >> tt;    // 테스트 케이스 수 입력 (필요 시)

    while (tt--) {
        solve();
    }
    return 0;
}