[BOJ] C++ 14891: 톱니바퀴 - 무난한 시뮬레이션

14891번: 톱니바퀴

---

문제가 요구하는 내용들을 그대로 하나씩 구현하면 된다. 딱 봐도 디버깅이 매우 귀찮아 보인다. 천천히 실수가 없게끔 구현해 보자.

 

톱니바퀴가 4개 고정돼 있고, 최대 100번 회전한다. 한 번의 회전이 일어나면 4개 모두 회전할 수 있는데, 데이터가 매우 적어서 시간복잡도 계산도 안 하고 바로 완전탐색으로 구현했다. 

 

문제의 요구사항은 다음과 같다.

1. 회전시키기
   k번째 톱니바퀴를 회전시키려면 그냥 새 배열을 만들어서 회전시킨 결과물을 저장하면 끝이다.
2. 근처 톱니바퀴 회전시킬지 정하기
   k번이 회전하면 k-1, k+1번을 회전시킬지 정해야 한다. k [6]과 k-1 [2]를 비교하면 되고, k [2]와 k+1 [6]을 비교하면 된다. 그리고 k-1이 회전됐다면 또, k와 k-2를 비교해야 하는데 k는 이미 회전시켰으므로 방문 표시할 배열도 필요하다. 또 k -> k-1 -> k+1 -> k-2 이런 식의 순회는 bfs이므로 큐를 사용하면 좋을 것 같다.

딱 여기까지만 생각해 놓고 바로 구현해 보자.

 

먼저 idx번 기어를 dir 방향으로 회전시키는 함수이다. 방향에 맞게 새 배열을 만들었는데, 상당히 헷갈려서 출력을 하면서 구현했다.

void rotate(int idx, int dir)
{
    // idx번 기어를 회전시키면 되는데, dir이 1이면 시계 -1이면 반시계
    char new_gear[8];
    if (dir == 1)
        // 시계
        for (int i = 0; i < 8; i++)
            new_gear[i] = gear[idx][(i + 7) % 8];
    else
        // 반시계
        for (int i = 0; i < 8; i++)
            new_gear[i] = gear[idx][(i + 1) % 8];

    for (int i = 0; i < 8; i++)
        gear[idx][i] = new_gear[i];
}

 

다음은 idx 기어를 시작으로 양 옆 기어들을 회전 시켜야 하는지 확인하는 함수이다. 그렇게 어려운 부분은 없고 그냥 bfs 느낌으로 구현하면 된다.

void check_gear(int idx, int dir)
{
    // idx번 기어를 dir방향으로 회전시키고 양 옆 확인
    bool visited[4] = {
        false,
    };
    queue<pair<int, int>> q;

    q.push({idx, dir});
    visited[idx] = true;

    while (!q.empty())
    {
        int cur_idx = q.front().first;
        int cur_dir = q.front().second;
        q.pop();
        //  cur_idx를 cur_dir 방향으로 회전시키고 양 옆을 확인하자.
        //  회전시키기 전에 양 옆을 확인해야 한다.
        int right_idx = cur_idx + 1;
        if (right_idx < 4 && !visited[right_idx])
        {
            // 오른쪽 기어가 있고, 방문하지 않았다면 체크
            if (gear[cur_idx][2] != gear[right_idx][6])
            {
                q.push({right_idx, cur_dir * -1});
                visited[right_idx] = true;
            }
        }
        int left_idx = cur_idx - 1;
        if (left_idx >= 0 && !visited[left_idx])
        {
            // 왼쪽 기어가 있고, 방문하지 않았다면 체크
            if (gear[cur_idx][6] != gear[left_idx][2])
            {
                q.push({left_idx, cur_dir * -1});
                visited[left_idx] = true;
            }
        }
        rotate(cur_idx, cur_dir);
    }
}

 

합쳐주면 끝! 지금까지 푼 시뮬레이션보다 요구 사항도 상당히 적었고 데이터 수가 워낙 적어서 완전 탐색으로 처음부터 갈피를 잡기 쉬운 문제였다.

/** 시뮬레이션 14891 톱니바퀴 **/
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <string>
using namespace std;

string gear[4];
int k;

void rotate(int idx, int dir)
{
    // idx번 기어를 회전시키면 되는데, dir이 1이면 시계 -1이면 반시계
    char new_gear[8];
    if (dir == 1)
        // 시계
        for (int i = 0; i < 8; i++)
            new_gear[i] = gear[idx][(i + 7) % 8];
    else
        // 반시계
        for (int i = 0; i < 8; i++)
            new_gear[i] = gear[idx][(i + 1) % 8];

    for (int i = 0; i < 8; i++)
        gear[idx][i] = new_gear[i];
}

void check_gear(int idx, int dir)
{
    // idx번 기어를 dir방향으로 회전시키고 양 옆 확인
    bool visited[4] = {
        false,
    };
    queue<pair<int, int>> q;

    q.push({idx, dir});
    visited[idx] = true;

    while (!q.empty())
    {
        int cur_idx = q.front().first;
        int cur_dir = q.front().second;
        q.pop();
        //  cur_idx를 cur_dir 방향으로 회전시키고 양 옆을 확인하자.
        //  회전시키기 전에 양 옆을 확인해야 한다.
        int right_idx = cur_idx + 1;
        if (right_idx < 4 && !visited[right_idx])
        {
            // 오른쪽 기어가 있고, 방문하지 않았다면 체크
            if (gear[cur_idx][2] != gear[right_idx][6])
            {
                q.push({right_idx, cur_dir * -1});
                visited[right_idx] = true;
            }
        }
        int left_idx = cur_idx - 1;
        if (left_idx >= 0 && !visited[left_idx])
        {
            // 왼쪽 기어가 있고, 방문하지 않았다면 체크
            if (gear[cur_idx][6] != gear[left_idx][2])
            {
                q.push({left_idx, cur_dir * -1});
                visited[left_idx] = true;
            }
        }
        rotate(cur_idx, cur_dir);
    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    for (int i = 0; i < 4; i++)
        cin >> gear[i];

    cin >> k;
    for (int i = 0; i < k; i++)
    {
        int gear_index, dir;
        cin >> gear_index >> dir;
        // dir이 1이면 시계 -1이면 반시계 회전
        check_gear(gear_index - 1, dir);
    }

    int ans = 0;
    ans += gear[0][0] - '0';
    ans += (gear[1][0] - '0') * 2;
    ans += (gear[2][0] - '0') * 4;
    ans += (gear[3][0] - '0') * 8;
    cout << ans << '\n';
}