[백준 알고리즘] 14891번 톱니바퀴(삼성 기출)

이번엔 삼성 SW역량 테스트 기출문제 14891번 톱니바퀴를 준비해보았습니다!!!

문제가 꽤 기네요!!!

문제를 간략하게 보면 톱니바퀴 4개를 돌릴 껀데 다 돌려서 최종 결과를 수치화 해서 보여주시오. 이것입니다.

먼저 문제를 설계하기 위한 여러가지를 생각해봅시다.

---

1. 톱니바퀴 정보를 저장할 변수 등 여러가지 변수
2. 함수 설계
3. 사용할 알고리즘(배경)
4. 톱니바퀴를 돌리고, 영향을 받는다고 할때 어떻게 돌아갈까?

---

간략하게 3개 정도 볼 수 있겠네요. 전 먼저 배경이 될 알고리즘으로는 BFS를 생각하였습니다. BFS는 주변을 먼저 살피자 라는 느낌이 있으니까용ㅎㅎ

그러면 사용할 변수들을 생각해봅시다. 톱니바퀴는 4개 고정, 8개의 톱니를 가지니까 4개의 톱니바퀴 배열(길이는 8)로 생각할 수 있죠. 저는 접근에 용이하도록 2차원 배열로 사용했어요. 그리고 톱니바퀴를 돌리는 여부를 체크할 변수도 필요하겠죠?

그 다음에 톱니바퀴를 돌리면 주변 톱니바퀴가 가지는 영향에 대해서 한번 알아봅시다.

삼성의 톱니바퀴는 일반 톱니바퀴랑 좀 다르게 같은 방향으로 움직여서 역 방향 회전이 되네요!!!

자, 마지막으로 함수의 설계입니다. 함수는 어떤 역할을 해야 하나요?? 여러분이 설계하는 방향에 따라 다르지만, 제 설계를 설명하면 이렇게

---

1. 매개변수 톱니바퀴 위치, 회전 방향
2. 회전 방향에 맞춰서 먼저 회전 시키기
3. 오른쪽 톱니바퀴가 있고, 회전 조건에 만족한다면 다시 오른쪽 톱니바퀴와 역 회전 방향으로 함수 호출
4. 왼쪽 톱니바퀴가 있고, 회전 조건에 만족한다면 다시 왼쪽 톱니바퀴와 역 회전 방향으로 함수 호출

---

전 이렇게 재귀를 사용하여 설계해보았습니다. 어떤 분들은 BFS에 걸맞게 queue로 설계하신 분도 계시고 다양 하더라구요!!

전 코딩할 때 변수가 길게 되더라도 변수 이름을 한번에 알아보기 편하게 짓는 편이에요. 옛날에 한글자 두글자로 지었다가 갈팡질팡한 적이 많아서..ㅎㅎㅎ

함수 코드를 한번 봅시다!

int chainSaw[5][8];
bool visit[5] = {false,};

void Rotate(int chainNum, int clock)
{
    visit[chainNum] = true;
    int prev2 = chainSaw[chainNum][2];
    int prev6 = chainSaw[chainNum][6];

    if(clock == 1) //시계방향으로 회전
    {
        int temp = chainSaw[chainNum][7];
        for(int i=6; i>=0; i--)
        {
            chainSaw[chainNum][i+1] = chainSaw[chainNum][i];
        }
        chainSaw[chainNum][0] = temp;
    }
    else if(clock == -1) //반시계방향으로 회전
    {
        int temp = chainSaw[chainNum][0];
        for(int i=1; i<8; i++)
        {
            chainSaw[chainNum][i-1] = chainSaw[chainNum][i];
        }
        chainSaw[chainNum][7] = temp;
    }
    //왼쪽에 톱니바퀴가 있고, N<->S로 만난다면
    if((chainNum-1>=1)&&(prev6 != chainSaw[chainNum-1][2])&&(visit[chainNum-1]==false))
        Rotate(chainNum-1,clock*-1);
    //오른쪽에 톱니바퀴가 있고, N<->S로 만난다면
    if((chainNum+1<=4)&&(prev2 != chainSaw[chainNum+1][6])&&(visit[chainNum+1]==false))
        Rotate(chainNum+1,clock*-1);
}

설계할때 실수를 몇 가지 했는데.. 고찰하자면

---

1. 회전 for loop 이상한 순서로 값 저장해서 이상해진 것
2. 톱니바퀴를 체크했는지 여부를 안 둬서 톱니바퀴가 전부 멈출때 까지 돌게 한 것
3. visit변수를 초기화 제대로 안 했던 점

---

우리 꼼꼼하게 설계합시닷!!!!헤헤헤헤 전체 코드는 아래 주소입니다~!!! 모두 파이팅~

full code