[Algorithm] 특이한 자석 (SW Expert Academy – 4013)

출처

• https://www.swexpertacademy.com

난이도

• 하 – (중) – 상 – 최상 – 풀지 못함

문제 (항상 대략적인 설명만 작성합니다. 문제는 위 출처에서 확인하세요)

• 톱니바퀴 모양의 자석이 4개 연결되어 있다. 특정 위치의 자석을 움직이면 앞에 위치하는 자석 또는 뒤에 위치하는 자석의 위치가 변경될 수도 있고, 전혀 움직이지 않을 수도 있다. 자석들을 몇 번씩 움직였을 때 최종 자석들의 위치를 계산하는 문제이다.
• SW Expert Academy의 경우 문제 공개를 하면 안 된다고 되어있어서 상세히 문제를 설명하지 않았다. 상세한 내용은 위 사이트에서 확인 부탁합니다.

후기

• 우선 아주 어렵지는 않았다. 이전의 차량 정비소, 미생물 문제와 비슷하게 매번 톱니바퀴를 움직였을 때의 움직임을 파악하여 최종 톱니바퀴의 위치를 찾으면 된다.
• 조금 어렵다고 판단했던 부분은 톱니바퀴를 움직임을 Recursive 함수를 사용하여 구현하는 부분이다. 중간에 위치한 톱니바퀴의 방향을 변경하는 경우 양쪽에 위치한 톱니바퀴 방향 계산을 위해 Recursive 함수를 2번 호출해야 하는 부분에서 약간의 어려움이 있었다.
• 이와 더불어 현재 톱니바퀴의 모양에 따라 미래의 톱니바퀴 모양이 달라지기 때문에 Recursive 함수를 먼저 호출하고 함수를 종료하기 이전에 톱니바퀴의 방향을 최종적으로 변경하도록 구현하였다. 이 부분이 기존의 다른 Recursive 함수 구현과 약간은 다른점이라고 판단된다.

코드

• 단순 Recursive 함수를 사용한 코드
• 실행 시간: 2ms (제일 빠른 코드 대비 2배 (1ms) 느림)

#include <stdio.h>

//MK: Visual Studio를 사용시 scanf 에러 제거함.
#pragma warning(disable:4996)

#define NEG(a) -(a)

int inputList[5][8];

int ptr[6];

int round;

int dir[2] = { -1, 1 };


//MK: 단순 Recursive함수를 사용하여 모든 톱니 바퀴의 움직임을 파악
void moveDir(int id, int dir, int prev) {
	if (id <= 0 || id >= 5 || dir == 0) {
		return;
	}
	int nextDir = dir * -1;
	if (prev == 0) {
		moveDir(id - 1, nextDir, id);
		moveDir(id + 1, nextDir, id);
		//MK: 다른 톱니 바퀴의 연산이 완료후 최종적으로 현재 톱니 바퀴 위치 변경
		ptr[id] -= dir;
	}
	else {
		//MK: 오른쪽 방향으로 이동하는 경우
		if(prev < id){
			int rDir = ptr[id-1] + 2;
			if (rDir >= 8) {
				rDir -= 8;
			}
			int lDir = ptr[id] - 2;
			if (lDir < 0) {
				lDir += 8;
			}
			if (inputList[id-1][rDir] != inputList[id][lDir]) {
				moveDir(id + 1, nextDir, id);
				ptr[id] -= dir;
			}
		}
		//MK: 왼쪽 방향으로 이동하는 경우
		else {
			int rDir = ptr[id] + 2;
			if (rDir >= 8) {
				rDir -= 8;
			}
			int lDir = ptr[id+1] - 2;
			if (lDir < 0) {
				lDir += 8;
			}
			if (inputList[id][rDir] != inputList[id+1][lDir]) {
				moveDir(id - 1, nextDir, id);
				ptr[id] -= dir;
			}
		}
	}
	if (ptr[id] >= 8) {
		ptr[id] -= 8;
	}
	else if (ptr[id] < 0) {
		ptr[id] += 8;
	}
}

int finalSolution() {
	int ret = 0;
	int sum[5] = { 0, 1, 2, 4, 8 };
	for (int i = 1; i < 5; i++) {
		if (inputList[i][ptr[i]] == 1)
			ret += sum[i];
	}
	return ret;
}

int main(void)
{
	int test_case;
	int T;
	//MK: input.txt로 부터 파일을 읽어오기 위해 구현 필요
	//freopen("input.txt", "r", stdin);
	setbuf(stdout, NULL);
	scanf("%d", &T);
	for (test_case = 1; test_case <= T; ++test_case)
	{
		scanf("%d", &round);
		for (int i = 1; i <= 4; i++) {
			for (int j = 0; j < 8; j++) {
				scanf("%d", &inputList[i][j]);
			}
		}
		ptr[1] = 0; ptr[2] = 0; ptr[3] = 0; ptr[4] = 0;
		for (int i = 0; i < round; i++) {
			int id;
			int dir;
			scanf("%d %d", &id, &dir);
			moveDir(id, dir, 0);
		}
		printf("#%d %d\n", test_case, finalSolution());
	}
	return 0; 
}