백준 9079 동전 게임

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

#include <iostream>
#include <vector>
#include <cmath>

#define INF 987654321

using namespace std;


int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int t;
    cin >> t;

    for (int test = 0; test < t; test++) {

        vector<vector<char>> board(3, vector<char>(3));

        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                cin >> board[i][j];
            }
        }

        int ans=INF;

        //1, 2, 3행, 1, 2, 3열, 좌측 대각선, 우측 대각선 순서
        for (int b = 1; b < round(pow(2, 8)); b++) {

            vector<vector<char>> temp=board;

            int cnt = 0;

            for (int i = 0; i < 8; i++) {
                if (b & (int) round(pow(2, i))) {
                    cnt++;
                    //행 뒤집기
                    if (i < 3) {
                        int w = i % 3;

                        for (int j = 0; j < 3; j++) {
                            if (temp[w][j] == 'T') {
                                temp[w][j] = 'H';
                            } else if (temp[w][j] == 'H') {
                                temp[w][j] = 'T';
                            }
                        }
                    }
                        //열 뒤집기
                    else if (i < 6) {
                        int h = i % 3;

                        for (int j = 0; j < 3; j++) {
                            if (temp[j][h] == 'T') {
                                temp[j][h] = 'H';
                            } else if (temp[j][h] == 'H') {
                                temp[j][h] = 'T';
                            }
                        }
                    }
                        //대각선 뒤집기
                    else {

                        //좌측 대각선 뒤집기
                        if (i == 6) {

                            for (int j = 0; j < 3; j++) {
                                if (temp[j][j] == 'T') {
                                    temp[j][j] = 'H';
                                } else if (temp[j][j] == 'H') {
                                    temp[j][j] = 'T';
                                }
                            }

                        } else if (i == 7) {
                            for (int j = 0; j < 3; j++) {
                                if (temp[j][2 - j] == 'T') {
                                    temp[j][2 - j] = 'H';
                                } else if (temp[j][2 - j] == 'H') {
                                    temp[j][2 - j] = 'T';
                                }


                            }

                        }

                    }
                }


                char c = temp[0][0];
                bool can = true;

                for (int i = 0; i < 3; i++) {
                    for (int j = 0; j < 3; j++) {
                        if (c != temp[i][j]) {
                            can = false;
                            break;
                        }
                    }
                }

                if (can) {
                    ans = min(ans, cnt);
                }

            }


        }


        if (ans != INF) {
            cout << ans << "\n";
        } else {
            cout << -1 << "\n";
        }

    }



    return 0;
}

 

1. 문제

동전 9개가 3*3으로 앞, 뒷면으로 주어진다. 이를 한 번에 한 줄(가로, 세로, 대각선) 뒤집는 과정을 반복해 모든 동전을 같은 방향으로 만들려고 하는데, 이를 위한 최소 횟수를 구하는 문제이다.

2. 풀이

브루트포스 문제이다. 한번의 연산에 각 줄에 대해 뒤집는 연산을 하고, 연산 이후 모든 동전이 같은 방향인지 확인하는 과정을 반복하면 된다.

 for (int b = 1; b < round(pow(2, 8)); b++)

 한 번의 연산은 1, 2, 3열, 1, 2, 3행, 좌측 대각선, 우측 대각선으로 총 8가지의 연산이 존재하므로 8자리 비트 내에서 연산을 진행한다.

 

    vector<vector<char>> temp=board;

            int cnt = 0;

            for (int i = 0; i < 8; i++) {
                if (b & (int) round(pow(2, i))) {
                    cnt++;
                    //행 뒤집기
                    if (i < 3) {
                        int w = i % 3;

                        for (int j = 0; j < 3; j++) {
                            if (temp[w][j] == 'T') {
                                temp[w][j] = 'H';
                            } else if (temp[w][j] == 'H') {
                                temp[w][j] = 'T';
                            }
                        }
                    }
                        //열 뒤집기
                    
                        //대각선 뒤집기
                    
                    }
                }

  처음 동전의 상태를 저장하고, 연산의 횟수를 저장한다. 비트의 각 자리를 보며 해당 연산을 해야 하면 연산 횟수를 증가시키고, 해당 위치의 동전에 대해 동전을 뒤집는 연산을 진행한다.

                char c = temp[0][0];
                bool can = true;

                for (int i = 0; i < 3; i++) {
                    for (int j = 0; j < 3; j++) {
                        if (c != temp[i][j]) {
                            can = false;
                            break;
                        }
                    }
                }

                if (can) {
                    ans = min(ans, cnt);
                }

 이후 각 위치를 돌면서 모든 동전이 같은지 확인하고, 같을 경우 ans를 갱신한다. 연산이 끝나고 최종 ans를 출력하면 정답을 구할 수 있다.