[ 백준 ] 14891 / 톱니바퀴

金弘均·2021년 9월 16일
0

Baekjoon Online Judge

목록 보기
142/228
post-thumbnail

# Appreciation

/*
 * Problem :: 14891 / 톱니바퀴
 *
 * Kind :: Simulation
 *
 * Insight
 * - 시계방향으로 회전, 반시계방향으로 회전 시
 *   맨 앞이나 뒤의 톱니를 넣었다 뺐다 해야되니까
 *   Deque 을 쓰는 게 좋을 것 같다
 *
 * - 톱니바퀴가 회전할 때 그 왼쪽, 오른쪽 톱니바퀴의 회전 여부는
 *   BFS 의 방문처리를 통해 다루어 주도록 하자
 *   (아래는 예시로 든 바퀴의 방문 처리 및 회전 흐름)
 *   + 1번 바퀴를 시계방향으로 돌릴 때,
 *     # 현재 : 1번 바퀴 => 1번 바퀴 방문 처리
 *       왼쪽의 0번 바퀴를 방문한 적 있는가
 *       => 0번 바퀴는 없다
 *       오른쪽의 2번 바퀴를 방문한 적 있는가
 *       => NO => 2번 바퀴도 돌아야 하나? => YES => 2번 바퀴 방문
 *     # 현재 : 2번 바퀴 => 2번 바퀴 방문 처리
 *       왼쪽의 1번 바퀴를 방문한 적 있는가
 *       => YES
 *       오른쪽의 3번 바퀴를 방문한 적 있는가
 *       => NO => 3번 바퀴도 돌아야 하나? => NO
 *     # 현재 : 2번 바퀴 => 회전 => 비(非)방문 처리
 *     # 현재 : 1번 바퀴 => 회전 => 비(非)방문 처리
 *
 * Point
 * - 문제는 바퀴를 1번 부터 세었지만
 *   편의상 코드는 0번 부터 세었다
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <deque>

using namespace std;

#define endl '\n'

// Set up : Global Variables
deque<char> W[4];

// Set up : Functions Declaration
void rotate(int no, int dir);


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    for (int i=0; i<4; i++) {
        W[i].resize(8);
        for (int j=0; j<8; j++) {
            cin >> W[i][j];
        }
    }

    // Process
    int K; cin >> K;
    for (int i=0; i<K; i++) {
        int no, dir;
        cin >> no >> dir; /* 문제는 1~4번 바퀴 */
        rotate(no-1, dir); /* 코드는 0~3번 바퀴 */
    }

    // Control : Output
    int ans = 0;
    for (int i=0; i<4; i++) {
        if (W[i][0] == '1') { /* N극은 '0', S극은 '1' */
            ans += (1<<i); /* 문제 기준 n 번 톱니바퀴 점수 = (n-1)^2 */
        }
    } cout << ans << endl;
}

// Helper Functions
void rotate(int no, int dir)
{
    /* 현재 no 번 바퀴 방문 처리 */
    isVisited[no] = true;

    /* 왼쪽 바퀴의 번호가 유효하고 방문된적 없으며 */
    if (no-1 >= 0 && not(isVisited[no-1])) {
        /* 현재 바퀴의 9시와 왼쪽 바퀴의 3시 극이 서로 다르다면 */
        if (W[no][6] != W[no-1][2]) {
            /* 왼쪽 바퀴 회전, 방향은 현재 바퀴의 방향과 반대 */
            rotate(no-1, -dir);
        }
    }

    /* 오른쪽 바퀴의 번호가 유효하고 방문된적 없으며 */
    if (no+1 < 4 && not(isVisited[no+1])) {
        /* 현재 바퀴의 3시와 오른쪽 바퀴의 9시 극이 서로 다르다면 */
        if (W[no][2] != W[no+1][6]) {
            /* 오른쪽 바퀴 회전, 방향은 현재 바퀴의 방향과 반대 */
            rotate(no+1, -dir);
        }
    }

    /* 주어진 방향에 따라 현재 바퀴 시계방향으로 회전 */
    if (dir == 1) {
        W[no].push_front(W[no].back());
        W[no].pop_back();
    }

    /* 주어진 방향에 따라 현재 바퀴 반시계방향으로 회전 */
    if (dir == -1) {
        W[no].push_back(W[no].front());
        W[no].pop_front();
    }

    /* 현재 no 번 바퀴 비(非)방문 처리 */
    isVisited[no] = false;
}
profile
이런 미친 게임을 봤나! - 옥냥이

0개의 댓글