14891번-톱니바퀴

문제

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

14891번: 톱니바퀴

---

접근방법

1) 접근 사고

1.입력값을 받습니다.

2.톱니바퀴와 방향을 입력받은 뒤

3.해당 톱니바퀴와 인접해 있는 톱니바퀴의 이동 방향을 계산한 뒤(인접해 있는 톱니바퀴가 움직일 경우 인접해 있는 톱니바퀴의 인접해 있는 톱니바퀴도) -> BFS를 활용하여 탐색하기

4.이동 방향이 저장된 배열을 활용해 톱니바퀴의 저장정보를 변경해줍니다.

 

2) 시간 복잡도

인접해 있는 톱니바퀴의 탐색들이 가장 많은 복잡도를 가지므로 O(V + E)로 해결됩니다.

 

3) 배운 점

개인적으로 BFS 알고리즘에 대해서 잘 알고 있다고 생각했는데 자만이었습니다. 처음에 어떻게 인접해 있는 톱니바퀴의 회전을 계산할 지 고민하는 시간이 길었습니다. 기존의 특유의 상하좌우로 탐색하는 문제에만 익숙해서 그런지 BFS를 사용할 생각을 못 했습니다. "탐색"이라는 키워드에 초점을 항상 두고 고민을 해야 할 꺼 같습니다.

 

4) PS

삼성 문제는 구현이 어질어질하다.

---

정답 코드

#include<bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pii pair<int,int>
#define mp(X,Y) make_pair(X,Y)
#define mt(X,Y) make_tuple(X,Y)
#define mtt(X,Y,Z) make_tuple(X,Y,Z)
#define ll long long
#define sz(v) (int)(v).size()
 
using namespace std;
 
int board[4][8];
int way[2] = {-1, 1};
int main(void)
{
    fastio;
    string str;
    for(int i = 0; i < 4; i++)
    {
        cin >> str;
        for(int j = 0; j < 8; j++)
            board[i][j] = str[j] - '0';
    }
 
    auto tobin_rotate = [&](int rotateWay[4]) -> void {
        //시계 방향일 경우의 회전
        for(int k = 0; k < 4; k++){
            if(rotateWay[k] == 1){
                int tmp = board[k][7];
                for(int i = 7; i >= 1; i--)
                    board[k][i] = board[k][i - 1];
                board[k][0] = tmp;
            }
            //반 시계 방향일 경우 회전
            else if(rotateWay[k] == -1)
            {
                int tmp = board[k][0];
                for(int i = 0; i < 7; i++)
                    board[k][i] = board[k][i + 1];
                board[k][7] = tmp;
            }
        }
    };
 
    auto operate = [&](int tobin, int dir){
        //전환할 톱니바퀴의 방향을 기억하는 배열
        int rotateWay[4] = {0,0,0,0};
        rotateWay[tobin] = dir;
 
        queue<pair<int,int>> q;
        int cur = tobin;
        for (int i = 0; i < 2; i++){
            if(tobin + way[i] >= 0 && tobin + way[i] < 4)
                q.push({cur, tobin + way[i]});
        }
 
        //BFS탐색을 통한 이동되는 톱니바퀴 탐색과 방향 지정
        while(!q.empty())
        {
            int start = q.front().first;
            int end = q.front().second;
            q.pop();
            
            int small = start < end ? start : end;
            int big = start < end ? end : start;
            
            //현재 톱니바퀴와 인접하는 톱니바퀴의 방향이 같을 경우 움직이지 않으므로 continue
            if(board[small][2] == board[big][6])
                continue;
            //인접해 있는 톱니바퀴는 현재 회전되는 톱니바퀴의 반대방향으로 회전
            rotateWay[end] = -(rotateWay[start]);
            for(int i = 0; i< 2; i++){
                int next = end + way[i];
                if(next >= 0 && next < 4 && rotateWay[next] == 0)
                    q.push({end, next});
            }
        }
        //회전하는 방향이 저장된 rotateWay 배열을 이용해 톱니바퀴를 회전시킨다.
        tobin_rotate(rotateWay);
    };
 
    int k;
    cin >> k;
    for(int i = 0; i < k; i++){
        int tobin, dir;
        cin >> tobin >> dir;
        operate(tobin - 1, dir);
    }
 
    int ret = 0;
    for(int i = 0; i < 4; i++)
        ret += (board[i][0] == 1) ? pow(2, i) : 0;
    cout << ret<< "\n";
}