BOJ 14939 불 끄기

Table of Contents

📝 문제 정보
#

링크: https://www.acmicpc.net/problem/14939

🧐 관찰 및 접근
#

맨 윗줄을 어찌저찌 일처리를 끝냈다고 가정하자.
두번째 줄부터, 그 윗줄의 남은 전구를 끄는 방법은 해당 칸 아래의 스위치를 컨트롤 하는 방법이 유일하다.
이를 사용하면 맨 윗줄을 처리할 수 있는 방법 $= 2^{10} = 1024$가지에 대해 해볼 수 있고, 시뮬레이션은 $100 \times 100 = 10000$번으로 충분히 시간 내로 들어온다.
맨 아랫줄에 켜진 전구가 남아있으면 안됨에 유의한다.

💻 풀이
#

코드 (C++):

void solve(){
    vector<string> board(10);
    rep(i, 0, 10) cin >> board[i];

    int answer = 1e9;
    rep(bit, 0, 1<<10){
        vector<string> cboard = board;
        int cnt = 0;
        auto press = [&](int r, int c){
            cnt++;
            cboard[r][c] = (cboard[r][c] == 'O' ? 'X' : 'O');
            if(r > 0) cboard[r-1][c] = (cboard[r-1][c] == 'O' ? 'X' : 'O');
            if(r < 9) cboard[r+1][c] = (cboard[r+1][c] == 'O' ? 'X' : 'O');
            if(c > 0) cboard[r][c-1] = (cboard[r][c-1] == 'O' ? 'X' : 'O');
            if(c < 9) cboard[r][c+1] = (cboard[r][c+1] == 'O' ? 'X' : 'O');
        };
        rep(c, 0, 10) if(bit & (1 << c)) press(0, c);
        rep(r, 1, 10) rep(c, 0, 10) if(cboard[r-1][c] == 'O') press(r, c);
        bool ok = true;
        rep(c, 0, 10) if(cboard[9][c] == 'O') ok = false;
        if(ok) answer = min(answer, cnt);
    }
    if(answer == 1e9) cout << -1 << '\n';
    else cout << answer << '\n';
}

🔒

구현 코드 잠금

아래 쿠팡 링크를 방문하시면 코드가 공개됩니다.
광고 수익이 블로그 운영에 도움이 됩니다 🙏

🛒 쿠팡 방문하고 코드 보기

방문 후 잠금이 자동으로 해제됩니다

📝 문제 정보#

🧐 관찰 및 접근#

💻 풀이#

📝 문제 정보
#

🧐 관찰 및 접근
#

💻 풀이
#