백준 14891 톱니바퀴 C++

www.acmicpc.net/problem/14891

14891번: 톱니바퀴

 

최종 코드

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ14891.cpp

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

#include <iostream>
#include <deque>
#include <cmath>
using namespace std;
int wheels[4][8] = {0, };
int K;
deque<pair<int, int>> cmd;
deque<pair<int, int>> rotate_wh;
int score = 0;
void check_wheels(int num, int d){
    switch(num){
        case 0:
            //0-1
            if(wheels[0][2] != wheels[1][6]){
                rotate_wh.push_back(make_pair(1, -1*d));
                //1-2
                if(wheels[1][2] != wheels[2][6]){
                    rotate_wh.push_back(make_pair(2, d));
                    //2-3
                    if(wheels[2][2] != wheels[3][6]){
                        rotate_wh.push_back(make_pair(3, -1*d));
                    }
                }
            }
            break;
        case 1:
            //1-0
            if(wheels[1][6] != wheels[0][2]){
                rotate_wh.push_back(make_pair(0, -1*d));
            }
            //1-2
            if(wheels[1][2] != wheels[2][6]){
                rotate_wh.push_back(make_pair(2, -1*d));
                //2-3
                if(wheels[2][2] != wheels[3][6]){
                    rotate_wh.push_back(make_pair(3, d));
                }
            }
            break;
        case 2:
            //2-1
            if(wheels[2][6] != wheels[1][2]){
                rotate_wh.push_back(make_pair(1, -1*d));
                //1-0
                if(wheels[1][6] != wheels[0][2]){
                    rotate_wh.push_back(make_pair(0, d));
                }
            }
            //2-3
            if(wheels[2][2] != wheels[3][6]){
                rotate_wh.push_back(make_pair(3, -1*d));
            }
            break;
        case 3:
            //3-2
            if(wheels[3][6] != wheels[2][2]){
                rotate_wh.push_back(make_pair(2, -1*d));
                if(wheels[2][6] != wheels[1][2]){
                    rotate_wh.push_back(make_pair(1, d));
                    if(wheels[1][6] != wheels[0][2]){
                        rotate_wh.push_back(make_pair(0, -1*d));
                    }
                }
            }
            break;
    }
    return;
}
void rotate_wheels(){
    while(!cmd.empty()){
        rotate_wh.clear();
        rotate_wh.push_back(cmd.front());
        cmd.pop_front();
        check_wheels(rotate_wh.front().first, rotate_wh.front().second);
        while(!rotate_wh.empty()){
            int wh = rotate_wh.front().first;
            int d = rotate_wh.front().second;
            rotate_wh.pop_front();
            if(d == 1){
                int temp = wheels[wh][7];
                for(int i=6; i>=0; i--){
                    wheels[wh][i+1] = wheels[wh][i];
                }
                wheels[wh][0] = temp;
            }
            else{
                int temp = wheels[wh][0];
                for(int i=1; i<=7; i++){
                    wheels[wh][i-1] = wheels[wh][i];
                }
                wheels[wh][7] = temp;
            }
        }
    }
}
void cal_score(){
    for(int i=0; i<4; i++){
        if(wheels[i][0] == 1){
            score += pow(2, i);
        }
    }
}
int main(int argc, const char * argv[]) {
    for(int i=0; i<4; i++){
        int n;
        cin >> n;
        for(int j=7; j>=0; j--){
            wheels[i][j] = n % 10;
            n /= 10;
        }
    }
    cin >> K;
    for(int i=0; i<K; i++){
        int num, d;
        cin >> num >> d;
        cmd.push_back(make_pair(num-1, d));
    }
    rotate_wheels();
    cal_score();
    cout << score << endl;
    
    return 0;
}

---

풀이 과정

풀이 시간 1시간

 

#include <iostream>
#include <deque>
#include <cmath>
using namespace std;
int wheels[4][8] = {0, };
int K;
//회전시킨 방법을 담는 덱, [톱니바퀴의 번호, 방향(1=시계방향,-1=반시계방향)]
deque<pair<int, int>> cmd;
//회전시킨 방법마다 회전이 일어나는 톱니바퀴의 번호와 방향을 담는 덱
deque<pair<int, int>> rotate_wh;
int score = 0;
void check_wheels(int num, int d){
	//첫 회전이 일어날 톱니바퀴의 번호에 따라 나머지 톱니바퀴의 회전 여부를 살핀다
    //톱니바퀴가 맞물리는 2번과 6번 톱니만 살피면 된다
    switch(num){
    	//0번 톱니바퀴
        case 0:
            //0-1 0번과 1번의 극을 살핀다 -> 극이 다른 경우 1번 톱니바퀴는 d의 반대방향으로 회전해야 한다
            if(wheels[0][2] != wheels[1][6]){
                rotate_wh.push_back(make_pair(1, -1*d));
                //1-2 1번과 2번의 극을 살핀다 -> 극이 다른 경우 2번 톱니바퀴는 d 방향으로 회전해야 한다
                if(wheels[1][2] != wheels[2][6]){
                    rotate_wh.push_back(make_pair(2, d));
                    //2-3 2번과 3번의 극을 살핀다 -> 극이 다른 경우 3번 톱니바퀴는 d의 반대 방향으로 회전해야 한다
                    if(wheels[2][2] != wheels[3][6]){
                        rotate_wh.push_back(make_pair(3, -1*d));
                    }
                }
            }
            break;
        //1번 톱니바퀴
        case 1:
            //1-0 1번과 0번의 극을 살핀다 -> 극이 다른 경우 0번 톱니바퀴는 d의 반대방향으로 회전해야 한다
            if(wheels[1][6] != wheels[0][2]){
                rotate_wh.push_back(make_pair(0, -1*d));
            }
            //1-2 1번과 2번의 극을 살핀다 -> 극이 다른 경우 2번 톱니바퀴는 d의 반대방향으로 회전해야 한다
            if(wheels[1][2] != wheels[2][6]){
                rotate_wh.push_back(make_pair(2, -1*d));
                //2-3 2번과 3번의 극을 살핀다 -> 극이 다른 경우 3번 톱니바퀴는 d방향으로 회전해야 한다
                if(wheels[2][2] != wheels[3][6]){
                    rotate_wh.push_back(make_pair(3, d));
                }
            }
            break;
        //2번 톱니바퀴
        case 2:
            //2-1 2번과 1번 톱니바퀴를 살핀다 -> 극이 다른 경우 1번 톱니바퀴는 d의 반대 방향으로 회전해야 한다
            if(wheels[2][6] != wheels[1][2]){
                rotate_wh.push_back(make_pair(1, -1*d));
                //1-0 1번과 0번 톱니바퀴를 살핀다 -> 극이 다른 경우 0번 톱니바퀴는 d 방향으로 회전해야 한다
                if(wheels[1][6] != wheels[0][2]){
                    rotate_wh.push_back(make_pair(0, d));
                }
            }
            //2-3 2번과 3번 톱니바퀴를 살핀다 -> 극이 다른 경우 3번 톱니바퀴는 d의 반대 방향으로 회전해야 한다
            if(wheels[2][2] != wheels[3][6]){
                rotate_wh.push_back(make_pair(3, -1*d));
            }
            break;
        case 3:
            //3-2 3번과 2번 톱니바퀴를 살핀다 -> 극이 다른 경우 2번 톱니바퀴는 d의 반대 방향으로 회전해야 한다
            if(wheels[3][6] != wheels[2][2]){
                rotate_wh.push_back(make_pair(2, -1*d));
                //2-1 2번과 1번 톱니바퀴를 살핀다 -> 극이 다른 경우 1번 톱니바퀴는 d 방향으로 회전해야 한다
                if(wheels[2][6] != wheels[1][2]){
                    rotate_wh.push_back(make_pair(1, d));
                    //1-0 1번과 0번 톱니바퀴를 살핀다 -> 극이 다른 경우 0번 톱니바퀴는 d의 반대 방향으로 회전해야 한다
                    if(wheels[1][6] != wheels[0][2]){
                        rotate_wh.push_back(make_pair(0, -1*d));
                    }
                }
            }
            break;
    }
    return;
}
void rotate_wheels(){
    while(!cmd.empty()){
        rotate_wh.clear();
        
        //회전시켜야하는 첫 톱니바퀴의 번호와 방향을 담는다
        rotate_wh.push_back(cmd.front());
        cmd.pop_front();
        
        //연쇄적으로 회전이 발생하는 톱니바퀴를 찾아서 rotate_wh 덱에 추가한다
        check_wheels(rotate_wh.front().first, rotate_wh.front().second);
        
        //rotate_wh에 담긴 정보대로 톱니바퀴를 회전시킨다
        while(!rotate_wh.empty()){
        	//wh = 톱니바퀴 번호, d = 회전 방향
            int wh = rotate_wh.front().first;
            int d = rotate_wh.front().second;
            rotate_wh.pop_front();
            //시계 방향으로 회전
            if(d == 1){
                int temp = wheels[wh][7];
                for(int i=6; i>=0; i--){
                    wheels[wh][i+1] = wheels[wh][i];
                }
                wheels[wh][0] = temp;
            }
            //반시계 방향으로 회전
            else{
                int temp = wheels[wh][0];
                for(int i=1; i<=7; i++){
                    wheels[wh][i-1] = wheels[wh][i];
                }
                wheels[wh][7] = temp;
            }
        }
    }
}
void cal_score(){
    for(int i=0; i<4; i++){
        if(wheels[i][0] == 1){
            score += pow(2, i);
        }
    }
}
int main(int argc, const char * argv[]) {
	//톱니바퀴의 상태 정보 초기화
    for(int i=0; i<4; i++){
        int n;
        cin >> n;
        //8개의 톱니의 상태 정보가 한 줄로 들어온다
        for(int j=7; j>=0; j--){
            wheels[i][j] = n % 10;
            n /= 10;
        }
    }
    cin >> K;
    for(int i=0; i<K; i++){
        int num, d;
        cin >> num >> d;
        cmd.push_back(make_pair(num-1, d));
    }
    rotate_wheels();
    cal_score();
    cout << score << endl;
    
    return 0;
}
//시간복잡도 = O(n), 공간복잡도 = O(n)

---

이전 풀이

풀이 시간  1시간 10분

//
//  main.cpp
//  BJ14891
//
//  Created by Hwayeon on 2021/01/22.
//
#include <iostream>
#include <queue>
#include <math.h>
using namespace std;

int wheel[4][8] = {0, };
int K;
int score = 0;
queue<pair<int, int>> r_q;

void rotate_now_wheel(int num, int dir){
    int prev, temp;
    switch (dir) {
        case -1:
            prev = wheel[num][0];
            for(int i=7; i>=0; i--){
                temp = wheel[num][i];
                wheel[num][i] = prev;
                prev = temp;
            }
            break;
        case 1:
            prev = wheel[num][7];
            for(int i=0; i<8; i++){
                temp = wheel[num][i];
                wheel[num][i] = prev;
                prev = temp;
            }
            break;
    }
}

void rotate_wheel(){
    while (!r_q.empty()) {
        int wh_num = r_q.front().first;
        int dir = r_q.front().second;
        int d_dir;
        queue<pair<int, int>> q;
        q.push(r_q.front());
        r_q.pop();
        if(dir == 1) d_dir = -1;
        else if(dir == -1) d_dir = 1;
        switch (wh_num) {
            case 0:
                if(wheel[wh_num][2] != wheel[wh_num+1][6]){
                    q.push(make_pair(wh_num+1, d_dir));
                    if(wheel[1][2] != wheel[2][6]){
                        q.push(make_pair(2, dir));
                        if(wheel[2][2] != wheel[3][6])
                            q.push(make_pair(3, d_dir));
                    }
                }
                break;
            case 1:
                if(wheel[wh_num][6] != wheel[wh_num-1][2]){
                    q.push(make_pair(wh_num-1, d_dir));
                }
                if(wheel[wh_num+1][6] != wheel[wh_num][2]){
                    q.push(make_pair(wh_num+1, d_dir));
                    if(wheel[2][2] != wheel[3][6]){
                        q.push(make_pair(3, dir));
                    }
                }
                break;
            case 2:
                if(wheel[wh_num][6] != wheel[wh_num-1][2]){
                    q.push(make_pair(wh_num-1, d_dir));
                    if(wheel[1][6] != wheel[0][2]){
                        q.push(make_pair(0, dir));
                    }
                }
                if(wheel[wh_num][2] != wheel[wh_num+1][6]){
                    q.push(make_pair(wh_num+1, d_dir));
                }
                break;
            case 3:
                if(wheel[wh_num][6] != wheel[wh_num-1][2]){
                    q.push(make_pair(wh_num-1, d_dir));
                    if(wheel[2][6] != wheel[1][2]){
                        q.push(make_pair(1, dir));
                        if(wheel[1][6] != wheel[0][2])
                            q.push(make_pair(0, d_dir));
                    }
                }
                break;
        }
        while(!q.empty()){
            int now_num = q.front().first;
            int now_dir = q.front().second;
            q.pop();
            rotate_now_wheel(now_num, now_dir);
        }
    }
    for(int i=0; i<4; i++){
        if(wheel[i][0] == 1) score += pow(2, i);
    }
}

int main(int argc, const char * argv[]) {
    for(int i=0; i<4; i++){
        int now_wh;
        cin >> now_wh;
        for(int j=7; j>=0; j--){
            wheel[i][j] = now_wh % 10;
            now_wh /= 10;
        }
    }
    cin >> K;
    for(int i=0; i<K; i++){
        int num, dir;
        cin >> num >> dir;
        r_q.push(make_pair(num-1, dir));
    }
    rotate_wheel();
    cout << score << endl;
    return 0;
}

 

1. 입력값 저장하기

 문제에서 주어지는 입력은 4개의 톱니바퀴의 상태와 회전 횟수 K, K개의 회전 방법이다. 이때 중요하게 해야할 처리가 두가지 있다.

 

• 4개의 톱니바퀴의 상태 입력 받아오기

    for(int i=0; i<4; i++){
        int now_wh;
        cin >> now_wh;
        for(int j=7; j>=0; j--){
            wheel[i][j] = now_wh % 10;
            now_wh /= 10;
        }
    }

 나는 4개의 톱니바퀴 상태를 저장하기 위해서 전역변수로 wheel[4][8]을 선언해줬다.

그리고 다른 문제를 풀면서 익숙했던 입력 방식처럼 cin >> wheel[i][j]으로 wheel[4][8]을 초기화 해줬는데, 입력이 잘 안 받아졌다.

예제를 자세히 살펴보니 각 톱니바퀴의 상태가 공백없이 8자리 숫자로 들어온다는 것을 깨달았다.

따라서 각 자리 수를 하나씩 뽑아내기 위해 먼저 now_wh에 8자리를 저장하고, 7번째 부터 0번째 인덱스까지 10으로 나눈 나머지를 담아줌으로써 톱니바퀴의 상태를 저장할 수 있었다.

 

• 회전 방법 Queue에 저장

    for(int i=0; i<K; i++){
        int num, dir;
        cin >> num >> dir;
        r_q.push(make_pair(num-1, dir));
    }

 나는 입력으로 주어진 톱니바퀴 회전 방법을 큐에 쌓고, pop() 하면서 톱니바퀴들을 회전시키는 방법으로 문제를 해결하였다.

따라서, 입력으로 들어오는 톱니바퀴 회전 방법(톱니바퀴의 번호, 방향)을 전역변수로 선언한 queue<pair<int, int>> r_q에 저장한다.

 

 

2. 톱니바퀴 회전시키기 rotate_wheel()

 이제, 톱니바퀴를 회전시켜보자.

문제 설명의 로직처럼 구현하기 위해서는 시작 톱니바퀴와 맞닿은 이웃 톱니바퀴의 극을 살펴보아야한다.

이때, 극이 다르면 서로 다른 방향으로 한 칸 회전한다. 이렇게 또 다른 톱니바퀴에서 회전이 일어나는 경우, 해당 톱니바퀴와 맞닿는 이빨의 극을 살펴 연쇄적으로 회전이 일어날지 아닌지를 살펴야한다.

여기서, 톱니바퀴에 회전이 일어나지 않으면 그와 맞닿는 다른 톱니바퀴에서도 회전이 일어나지 않는다는 점에 주의하자.

예를 들어, 4번 톱니바퀴를 시계방향으로 회전시킨 것을 시작으로, 3번 톱니바퀴에서 반시계 방향으로 회전이 일어났다고 해보자. 그러면, 3번과 맞닿는 2번 톱니바퀴에도 회전이 일어날지를 살펴야한다. 이때, 맞닿은 2번과 3번의 이빨의 극이 같다면, 2번에는 회전이 일어나지 않는다. 따라서, 2번과 맞닿은 1번 톱니바퀴도 회전이 일어나지 않을 것이므로 살펴보지 않아도 된다는 것이다.

void rotate_wheel(){
    while (!r_q.empty()) {
	int wh_num = r_q.front().first;
        int dir = r_q.front().second;
        int d_dir;
        queue<pair<int, int>> q;
        q.push(r_q.front());
        r_q.pop();
        if(dir == 1) d_dir = -1;
        else if(dir == -1) d_dir = 1;
        switch (wh_num) {
            case 0:
                if(wheel[wh_num][2] != wheel[wh_num+1][6]){
                    q.push(make_pair(wh_num+1, d_dir));
                    if(wheel[1][2] != wheel[2][6]){
                        q.push(make_pair(2, dir));
                        if(wheel[2][2] != wheel[3][6])
                            q.push(make_pair(3, d_dir));
                    }
                }
                break;
            case 1:
                if(wheel[wh_num][6] != wheel[wh_num-1][2]){
                    q.push(make_pair(wh_num-1, d_dir));
                }
                if(wheel[wh_num+1][6] != wheel[wh_num][2]){
                    q.push(make_pair(wh_num+1, d_dir));
                    if(wheel[2][2] != wheel[3][6]){
                        q.push(make_pair(3, dir));
                    }
                }
                break;
            case 2:
                if(wheel[wh_num][6] != wheel[wh_num-1][2]){
                    q.push(make_pair(wh_num-1, d_dir));
                    if(wheel[1][6] != wheel[0][2]){
                        q.push(make_pair(0, dir));
                    }
                }
                if(wheel[wh_num][2] != wheel[wh_num+1][6]){
                    q.push(make_pair(wh_num+1, d_dir));
                }
                break;
            case 3:
                if(wheel[wh_num][6] != wheel[wh_num-1][2]){
                    q.push(make_pair(wh_num-1, d_dir));
                    if(wheel[2][6] != wheel[1][2]){
                        q.push(make_pair(1, dir));
                        if(wheel[1][6] != wheel[0][2])
                            q.push(make_pair(0, d_dir));
                    }
                }
                break;
        }
        while(!q.empty()){
            int now_num = q.front().first;
            int now_dir = q.front().second;
            q.pop();
            rotate_now_wheel(now_num, now_dir);
        }
    }
    for(int i=0; i<4; i++){
        if(wheel[i][0] == 1) score += pow(2, i);
    }
}

 

 이제 하나씩 구현해보자.

 

• 처음으로 발생하는 회전 방법 pop() 하기

	int wh_num = r_q.front().first;
        int dir = r_q.front().second;
        int d_dir;
        queue<pair<int, int>> q;
        q.push(r_q.front());
        r_q.pop();
        if(dir == 1) d_dir = -1;
        else if(dir == -1) d_dir = 1;

 1. 처음으로 회전을 시키는 톱니바퀴의 번호와 방향을 r_q.front()에서 받아와 각각 wh_num, dir에 담아준다.

 2. 연쇄적으로 회전이 될 톱니바퀴의 번호와 방향을 담아주는 queue<pair<int, int>> q를 선언한다.

 3. r_q.front()를 q에 push 해주고 r_q를 pop 해준다.

 4. dir과 반대 방향인 d_dir를 초기화 한다.

 

 

• 연쇄 회전이 발생되는 톱니바퀴의 번호와 방향을 q에 push() 하기

	switch (wh_num) {
            case 0:
                if(wheel[wh_num][2] != wheel[wh_num+1][6]){
                    q.push(make_pair(wh_num+1, d_dir));
                    if(wheel[1][2] != wheel[2][6]){
                        q.push(make_pair(2, dir));
                        if(wheel[2][2] != wheel[3][6])
                            q.push(make_pair(3, d_dir));
                    }
                }
                break;
            case 1:
                if(wheel[wh_num][6] != wheel[wh_num-1][2]){
                    q.push(make_pair(wh_num-1, d_dir));
                }
                if(wheel[wh_num+1][6] != wheel[wh_num][2]){
                    q.push(make_pair(wh_num+1, d_dir));
                    if(wheel[2][2] != wheel[3][6]){
                        q.push(make_pair(3, dir));
                    }
                }
                break;
            case 2:
                if(wheel[wh_num][6] != wheel[wh_num-1][2]){
                    q.push(make_pair(wh_num-1, d_dir));
                    if(wheel[1][6] != wheel[0][2]){
                        q.push(make_pair(0, dir));
                    }
                }
                if(wheel[wh_num][2] != wheel[wh_num+1][6]){
                    q.push(make_pair(wh_num+1, d_dir));
                }
                break;
            case 3:
                if(wheel[wh_num][6] != wheel[wh_num-1][2]){
                    q.push(make_pair(wh_num-1, d_dir));
                    if(wheel[2][6] != wheel[1][2]){
                        q.push(make_pair(1, dir));
                        if(wheel[1][6] != wheel[0][2])
                            q.push(make_pair(0, d_dir));
                    }
                }
                break;
        }

  r_q.front()에 의해 톱니바퀴가 회전하면, 연쇄 회전이 일어날 곳을 찾아주기 위해 wh_num을 case로 한 switch문으로 구현했다.

1. wh_num과 맞닿은 톱니바퀴 이빨의 극이 다른지 확인하기 (wheel[wh_num][2] = 톱니바퀴의 오른쪽 이빨, wheel[wh_num][6] = 톱니바퀴의 왼쪽 이빨)
2. 극이 다르다면 반대 방향으로 회전해야 하므로 q.push(make_pair(해당 톱니바퀴의 번호, d_dir)) 해준다.
3. 2.에서 연쇄적으로 회전이 발생한 톱니바퀴와 맞닿은 다른 톱니바퀴도 살펴, 맞닿은 곳의 극이 다르다면 q.push(make_pair(해당 톱니바퀴의 번호, dir))을 해준다.(d_dir의 반대방향이 dir 이므로!)

 

• q에 담긴 톱니바퀴들 회전시키기

 이제 위의 과정을 통해 회전해야 하는 톱니바퀴의 번호와 방향이 담긴 queue<pair<int, int>> q에 따라 rotate_now_wheel()을 하여 각각의 톱니바퀴를 회전시키자.

        while(!q.empty()){
            int now_num = q.front().first;
            int now_dir = q.front().second;
            q.pop();
            rotate_now_wheel(now_num, now_dir);
        }

void rotate_now_wheel(int num, int dir){
    int prev, temp;
    switch (dir) {
        case -1:
            prev = wheel[num][0];
            for(int i=7; i>=0; i--){
                temp = wheel[num][i];
                wheel[num][i] = prev;
                prev = temp;
            }
            break;
        case 1:
            prev = wheel[num][7];
            for(int i=0; i<8; i++){
                temp = wheel[num][i];
                wheel[num][i] = prev;
                prev = temp;
            }
            break;
    }
}

1. 톱니바퀴의 번호 num과 dir을 매개변수로 받아온다.
2. 이전 톱니바퀴 이빨의 극을 저장하는 prev와 현재와 이전 이빨의 값을 바꿔주기 위해 필요한 temp를 선언한다.
3. 방향에 따라 switch case를 실행하여 톱니바퀴의 값을 업데이트한다.

 

• 점수 구하기 score

 위 과정을 r_q.empty() == true일 때까지 진행하면 입력으로 받아온 모든 회전을 발생시킨 것이다. 그렇다면 이제 점수를 구해보자.

    for(int i=0; i<4; i++){
        if(wheel[i][0] == 1) score += pow(2, i);
    }

4개의 톱니바퀴의 12시 방향이 S극(1)이면 점수가 발생한다.

점수는 1번인 경우, 1점, 2번은 2점, 3번은 4점, 4번은 8점이기 때문에 이 규칙에 따라 pow() 함수를 활용하여 2의 i 제곱근을 한 값을 score에 더해주도록 구현하였다.(pow()를 내장 함수로 가지는 cmath(=math.h) 라이브러리에 대해서는 아래 참고 자료를 살펴보면 된다.)

 

 

---

참고

• 2021/01/22 - [C++] - [STL] cmath(math.h)

[STL] cmath(math.h)