4013. 특이한 자석

static int K;
static list<int> magnetic[4]; //value: 0(N), 1(S)
static pair<int, int> rotation[8]; //magnetic info, direction(1: 시계, -1, 반시계)
static bool visit[4];
static int score[] = { 1, 2, 4, 8 };

//회전 시키려고 할 때 양 옆에 다른 극 이 있는 경우에는
//인력에 의해 반대 방향으로 회전됨.
static void __solution(int n, int d)
{
	if (visit[n])
		return;

	visit[n] = true;
	if (n - 1 >= 0) //왼쪽에 자석이 있으면
	{
		list<int>::reverse_iterator left = magnetic[n].rbegin();
		list<int>::iterator right = magnetic[n - 1].begin();

		left++; //reverse iterator가 가리키는 위치를 정확히 파악
		right++; right++;

		if (*left != *right) //다른 극이면
			__solution(n - 1, -d); //인력에 의해 회전시키기 위해 재귀 호출
	}
	if (n + 1 < 4) //오른쪽에 자석이 있으면
	{
		list<int>::iterator right = magnetic[n].begin();
		list<int>::reverse_iterator left = magnetic[n + 1].rbegin();

		right++; right++;
		left++; //reverse iterator가 가리키는 위치를 정확히 파악

		if (*left != *right) //다른 극이면
			__solution(n + 1, -d); //인력에 의해 회전시키기 위해 재귀 호출
	}

	if (d == 1) //시계 방향으로 회전
	{
		int last = magnetic[n].back(); //뒤에것이
		magnetic[n].pop_back();
		magnetic[n].push_front(last); //맨 앞으로
	}
	else //반시계 방향으로 회전
	{
		int first = magnetic[n].front(); //앞에것이
		magnetic[n].pop_front();
		magnetic[n].push_back(first); //맨 뒤로
	}
	visit[n] = false;
}

static int solution()
{
	int n, d, ans = 0;

	scanf("%d", &K);
	for (int i = 0; i < 4; i++)
	{
		for (int j = 0; j < 8; j++)
		{
			scanf("%d", &n);
			magnetic[i].push_back(n);
		}
	}

	for (int i = 0; i < K; i++)
	{
		scanf("%d %d", &n, &d); //회전 정보를 입력 받고,
		//자석의 번호는 1, 2, 3, 4로 주어지므로 -1 해서 사용
		__solution(n - 1, d); //회전 시킴
	}

	for (int i = 0; i < 4; i++)
	{
		if (magnetic[i].front() == 1) //S극이면
			ans += score[i]; //해당 자석의 할당된 값만큼 누적
	}

	for (int i = 0; i < 4; i++)
		magnetic[i].clear();

	return ans;
}

리스트를 이용하여 자석이 회전하는 것을 모델링 하였다.

다만, 반복자 사용 시 착각하고 있었던 부분이 있다.

 

reverse_iterator 사용 시 rebegin()이 가리키고 있는 지점은 리스트의 마지막 노드이다.

그러나 예제 그림을 보면서 rebegin()이 가리키고 있는 지점을 리스트의 첫번째 노드로 착각하고 있었다.

즉, 접점이 생기는 극을 찾기 위해 reverse_iterator에 대해서 ++ 연산을 두번하고 있었다.

그림으로 인해 착각했던 부분이었다. 

 

일반 iterator 사용 시 end()가 가리키고 있는 지점은 리스트의 마지막 노드 그 다음이다.

일반적으로 NULL인 노드로 생각하면 된다. 그러나 반복자는 end()에 대해서 --연산을 허용하고 있다.

즉, end()가 반환하는 반복자에 대해서 --연산을 하면 리스트의 마지막 노드를 가리킨다는 것이다.

반대로 reverse_iterator는 rend()에 대해 ++연산을 하면 리스트의 첫번째 노드를 가리키게 된다.

 

 

//주의사항 및 정리

1. 문제를 똑바로 읽고, 정확히 이해 할 것, 나는 자석을 먼저 움직이고 이로 인해 N극과 N극, 또는 S극과 S극이 만나 척력으로 인해 인접한 자석이 반대방향으로 움직이는 것인 줄로 이해하고 문제를 풀었다. 그러나 실제로는 두 자석이 서로다른 극으로 인해 인력이 작용하여 붙어있는 상태에서 임의의 자석을 움직이면 그 인력으로 인해 자석이 딸려 움직이는 현상을 모델링 해야 한다. 이 부분에 대해서는 나의 주관적인 생각이 들어가 동작방식을 잘못 이해하게 만들었다.

2. 아무래도 풀었던 문제를 다시 풀다보니, 문제를 제대로 읽지 않고 예전에 풀었던 기억을 더듬어서 문제를 다시 풀고 있는 듯한 느낌이 자꾸 들었다. 실제 시험에서는 처음 보는 문제이기 때문에 더 주의를 하리라 생각하지만 계속해서 풀었던 문제를 리뷰해나가는 과정에서 자꾸만 걸림돌이 될 것 같다.