[Baekjoon]14891.톱니바퀴

14891.톱니바퀴

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

14891번: 톱니바퀴

---

재귀함수를 이용해서 풀었다. 

 

먼저 톱니바퀴 배열을 2차원 배열로 생성하고 제일 먼저 회전시킬 톱니를 회전시킬때 인접한 톱니들의 상태를 확인해서 회전할 지 안할지를 결정한다. 이 문제에서 핵심은 회전하기 전에 모든 톱니의 회전여부가 결정된다는 것이다. 따라서 회전시키기 전에 모든 톱니의 회전방향이 결정된다. 

 

톱니 배열을 12시방향부터 시계방향으로 순서대로 0~7로 인덱싱하면 회전여부를 따질때 인접한 톱니의 2,6번의 극이 무엇인지만 체크하면 된다. 나는 톱니가 회전하는 과정을 직관적으로 이해하기 더 쉽게하기 위해서 메소드를 최대한 쪼개서 만들었다. 

 

explore메소드가 각 톱니의 회전여부를 결정하는 메소드인데 이것을 재귀함수를 이용했다. 처음에 회전시키는 톱니의 왼쪽과 오른쪽을 재귀적으로 탐색하면서 회전여부가 결정된다. 파라미터에 -dir이 있는 것은 처음에 회전시키는 톱니와 반대방향으로 회전해야 하기 때문에 -dir로 설정했다. 

explore메소드 개요

 

private static void explore(int n, int dir) {

		if (visited[n]) { // 탈출 조건
			return;
		}

		visited[n] = true;

		if (n - 1 >= 0 && cogwheel[n][6] != cogwheel[n - 1][2]) { // 왼쪽 톱니 탐색
			explore(n - 1, -dir);
		}
		if (n + 1 < 4 && cogwheel[n][2] != cogwheel[n + 1][6]) { // 오른쪽 톱니 탐색
			explore(n + 1, -dir);
		}
		
		visited[n] = false;
		rotate(n, dir);
	}

 

회전이 끝나고 스코어를 계산할 때 점수가 2의 거듭제곱 수인 것을 이용하기 위해 쉬프트 연산을 이용했다. n<<i 는 산술적으로 n*2^i 와 같음을 이용했다. 이 부분은 다른 사람들의 코드를 참고하여 코드를 간결하게 짜는데 도움이 되었다. 

 

<전체코드>