컴퓨터 공학 기초/알고리즘 (브루트포스)
백준 14891 (톱니바퀴)
JongSeok_12
2020. 7. 16. 21:47
https://www.acmicpc.net/problem/14891
14891번: 톱니바퀴
첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 �
www.acmicpc.net
풀이
해당 문제는 재귀를 사용하여 회전시킬 톱니바퀴의 위치와 -1 or + 1 위치에 해당하는 톱니바퀴의 마주보는 면을 비교하며 회전시킬지 말지 선택하여 풀면 되는 문제이다.
주의 사항
예를들어 하나의 톱니바퀴가 회전하고 인접한 위치의 다른 톱니바퀴가 회전해야 한다면 다른 위치의 톱니바퀴를 기준으로 또 다른 톱니바퀴가 회전하는 경우의 수 까지 구해야 한다.
즉 3 번이 회전하고 그에 따라 2번 톱니바퀴가 회전하고 그에 따라 1번 톱니바퀴 까지 회전하는 경우의 수가 존재할 수 있다.
따라서 재귀함수를 구현할 때 바로 해당 INDEX에 해당하는 톱니바퀴를 회전시키는게 아니라 먼저 인접한 톱니바퀴가 회전해야 하는가 ? 확인을 한 뒤 만약 회전해야 할 경우 재귀를 통해 회전시킬 톱니바퀴의 인접한 다른 톱니바퀴를 다시 비교 하는 과정을 계속 진행하며 모든 과정이 끝나고 더이상 회전시킬 톱니바퀴가 없을 때 재귀함수를 반환하며 반환시에 톱니바퀴를 회전시켜야한다.
즉 재귀를 타고 들어갈 때에는 돌리지 않고 회전시켜야 하는 모든 톱니바퀴가 어떤건지 구해졋을 때 재귀된 함수를 반환하며 톱니바퀴를 돌린다.
#include <iostream>
#include <string>
using namespace std;
char clock[4][9];
// 각 톱니바퀴의 중첩되는 경우를 거르기 위해 회전시킬 톱니바퀴의 Index에 check 할 배열
int used[4];
int cmdCnt;
struct Node{
int idx;
int dir;
};
Node cmdList[101];
void spin(int dir, int idx){
// y축은 dir로 고정
if (dir == 1){
// 시계 우측 밀기
char tmp = clock[idx][7];
for (int x = 7; x >= 1; --x){
clock[idx][x] = clock[idx][x - 1];
}
clock[idx][0] = tmp;
}
if (dir == -1){
// 반시계 좌측 밀기
char tmp = clock[idx][0];
for (int x = 0; x < 7; ++x){
clock[idx][x] = clock[idx][x + 1];
}
clock[idx][7] = tmp;
}
}
void dfs(int idx, int dir){
if (used[idx] == 0){
used[idx] = 1;
if (idx == 0){
// +1 우측 탐색 후 본인 회전
if (used[idx + 1] == 0){
if (clock[idx + 1][6] != clock[idx][2]){
if (dir == 1){
dfs(idx + 1, -1);
}
else{
dfs(idx + 1, +1);
}
}
}
spin(dir, idx);
}
else if (idx == 3){
// -1 좌측 탐색 후 본인 회전
if (used[idx - 1] == 0){
if (clock[idx - 1][2] != clock[idx][6]){
if (dir == 1){
dfs(idx - 1, -1);
}
else{
dfs(idx - 1, +1);
}
}
}
spin(dir, idx);
}
else{
// -1 좌측 +1 우측 전부 탐색 후 본인 회전
if (used[idx - 1] == 0){
if (clock[idx - 1][2] != clock[idx][6]){
if (dir == 1){
dfs(idx - 1, -1);
}
else{
dfs(idx - 1, 1);
}
}
}
if (used[idx + 1] == 0){
if (clock[idx + 1][6] != clock[idx][2]){
if (dir == 1){
dfs(idx + 1, -1);
}
else{
dfs(idx + 1, 1);
}
}
}
spin(dir, idx);
}
}
}
int main(){
//freopen_s(new FILE*, "tes.text", "r", stdin);
for (int i = 0; i < 4; ++i){
for (int j = 0; j < 8; ++j){
cin >> clock[i][j];
}
}
cin >> cmdCnt;
for (int i = 0; i < cmdCnt; ++i){
cin >> cmdList[i].idx >> cmdList[i].dir;
}
for (int i = 0; i < cmdCnt; ++i){
for (int j = 0; j < 4; ++j){
used[j] = 0;
}
dfs(cmdList[i].idx -1, cmdList[i].dir);
}
int num = 0;
if (clock[0][0] == '1') num += 1;
if (clock[1][0] == '1') num += 2;
if (clock[2][0] == '1') num += 4;
if (clock[3][0] == '1') num += 8;
printf("%d", num);
}