[백준] 14891번 톱니바퀴

문제

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

풀이

2시간 정도만에 주어진 테스트케이스 4개를 맞춰서 좋아한 문제다. 이상하게 계속 틀렸습니다가 뜨는데 몇시간동안 들여봐도 어디서 잘못된건지 몰랐다.

지금도 뭐가 다른지 모르겠다.

문제에서 톱니바퀴를 회전하는 부분을 보고 톱니바퀴의 정보를 덱(Deque)으로 저장했다.

문제에서 주의해야할 사항은 다음과 같다.

1. 현재 위치한 톱니바퀴는 무조건 회전한다.
2. 인접한 톱니바퀴는 극이 다를 경우만 반대방향으로 회전한다.

이 과정을 재귀함수로 구현했다.

아래 소스코드를 보면 이해하기가 쉽다.

처음에 소스코드를 짤 때는 Solution 함수에 들어갔을 때 현재 톱니바퀴의 정보를 curr_arr이라는 전역변수에 Copy 해주고 현재 톱니바퀴는 회전시킨 후에 인접한 톱니바퀴와 curr_arr배열을 비교하여 처리했다.

전역변수로 사용한 curr_arr[8]에서 문제가 발생했는지 따로 현재 상태를 저장하지않고 인접한 톱니바퀴를 검사한 후에 현재 톱니바퀴를 회전시켜주니까 맞았습니다 떳다. 아직도 뭐가 문제였는지는 모르겠다.

또 이상한 점은 Solution 함수 안에서 curr_arr[8]을 선언하고 지역변수로 현재 톱니바퀴 정보를 Copy하고 인접한 톱니바퀴와 curr_arr을 비교하니까 맞았습니다가 뜨긴했다.

소스코드

#include <iostream>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <deque>

using namespace std;

// 톱니바퀴 4개 정보
// 0 : N극, 1 : S극
deque<int> dq[5];
bool visited[5]; // 톱니바퀴 회전 여부
vector<pair<int, int>> vec_r; // k개의 회전 방법 (톱니바퀴 번호, 방향)
int k;

void RotateDq(int num, int direction)
{
    // 시계방향
    if (direction == 1)
    {
        int tmp = dq[num].back();
        dq[num].pop_back();
        dq[num].push_front(tmp);
    }
    // 반시계방향
    else if (direction == -1)
    {
        int tmp = dq[num].front();
        dq[num].pop_front();
        dq[num].push_back(tmp);
    }
}

void Solution(int num, int direction)
{
    visited[num] = true;

    int prev_num = num - 1, next_num = num + 1;

    // 이전 톱니바퀴
    if (prev_num > 0 && !visited[prev_num])
    {
        // 서로 다른 극이면
        if (dq[prev_num][2] != dq[num][6])
        {
            Solution(prev_num, direction * -1);
        }
    }

    // 다음 톱니바퀴
    if (next_num < 5 && !visited[next_num])
    { 
        // 서로 다른 극이면
        if (dq[next_num][6] != dq[num][2])
        {
            Solution(next_num, direction * -1);
        }
    }

    // 현재 톱니바퀴 회전
    RotateDq(num, direction);
}


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


    // #1. 톱니바퀴 상태 저장
    for (int i = 0; i < 4; i++)
    {
        string s;
        cin >> s;
        for (int j = 0; j < 8; j++)
        {
            int tmp = s[j] - '0';
            dq[i + 1].push_back(tmp);
        }
    }

    // #2. 회전 횟수
    cin >> k;

    // #3. 회전 방법
    for (int i = 0; i < k; i++)
    {
        // 시계방향 : 1, 반시계방향 : -1
        int dq_num, direction;
        cin >> dq_num >> direction;
        vec_r.push_back(make_pair(dq_num, direction));
    }

    // #4. 회전
    for (int i = 0; i < vec_r.size(); i++)
    {
        Solution(vec_r[i].first, vec_r[i].second);
        memset(visited, false, sizeof(visited));
    }

    int ans = 0;
    for (int i = 1; i < 5; i++)
    {
        if (dq[i][0] == 1)
            ans += pow(2, i - 1);
    }

    cout << ans << "\n";

    return 0;
}