BOJ2549 루빅의 사각형

 

2549번 루빅의 사각형

4×4 격자판이 있다.

행을 한 개 골라 아래쪽으로 k번(1≤k≤3) 움직이거나

열을 한 개 골라 오른쪽으로 k번(1≤k≤3) 움직이는 것을 한 번 움직인다고 한다.

격자판의 숫자가 주어질 때, 최소 횟수로 격자판을 움직여

1부터 16까지 순서대로 배열된 격자판으로 만드는 횟수(≤7)와 방법을 출력한다.

 

 

 

일단은, 되는대로 BFS를 돌려봤지만 역시 메모리 초과로 통과할 수 없었다.

한 번 움직이는 경우의 수는 8(행/열 개수)*3(k 개수)였고

아무리 정답이 7번 이내로 나온다 해도 24^7개의 경우를 확인하려니 당연히,,

몇 가지 최적화로 가짓수를 줄여봤지만 그래도 메모리초과였다.

---

방법 1. BFS + 양방향 탐색 + map

 

 

BFS로 찾되 양방향으로 탐색하기로 했다. 주어진 상태 input에서 도달 목표 goal이 되는 길을

input→A1→A2→...→S = T←...←B2←B1←goal

와 같이 input, goal 양쪽에서 각각 BFS를 시행하면서 탐색하는 방법이다.

 

움직이는 횟수만 구한다면 set을 이용하면 됐지만 어떻게 움직였는지도 구해야했기 때문에 map을 사용했다.

key는 격자판의 상태를 a부터 p까지의 문자로 표현한 string

value는 움직인 경로를 저장하는 vector<int>를 구조체로 했다.

 

map은 세 개가 필요하다.

변형할 원소가 들어있는 맵 비교 대상이 될 맵 변형된 원소를 저장할 맵

이번 시행에서 M[0]의 원소 s를 변형, M[1]의 원소 tar와 비교, M[2]에 삽입한다면

다음 시행에서는 M[1]의 원소 s를 변형, M[2]의 원소 tar와 비교, M[0]에 삽입하고

그다음 시행에서는 M[2]의 원소 s를 변형, M[0]의 원소 tar와 비교, M[1]에 삽입한다.

 

이걸 M[A]의 원소를 변형, M[B]의 원소와 비교, M[C]에 삽입한다고 일반화하자.

if(input==goal) 0 출력, 종료

ans=1, A=0, B=1, C=2
M[A].insert({input,h(empty vector)})
M[B].insert({goal,h(empty vector)})
while(1){
	for({s,h} in M[A]) {
		h.v.push_back(0)
		for(변형 방법) {
			s, h.v.back() 변형
            
			if(s in M[A]) continue
            
			tar=M[B].find(s)
			if(tar 없음) M[C].insert({s,h})
			else 정답 출력, 종료
		}
	}
	M[A].clear()
	ans++, A++, A%=3, B++, B%=3, C++, C%=3
}

 

이런 식으로 input이 goal에 도달하는 최소 횟수를 구하면

이동 방법을 출력할 때는 최소 횟수가 홀수인지 짝수인지에 따라 달리 해줘야 한다.

움직인 횟수가 홀수이면 이번 움직임은 input을 움직인 것이고

짝수이면 이번 움직임은 goal에서부터 거꾸로 움직인 것이기 때문

* goal의 1행을 오른쪽으로 3번 움직여 tar이 됐다는 건

   tar의 1행을 오른쪽으로 1번 움직여 goal이 된 것을 의미한다.

 

따라서 출력은 아래처럼 해준다.

	if (ans가 홀수) revh = tar->second;
	else revh = h, h = tar->second;

	ans 출력
	h.v의 원소를 순서대로, 횟수를 원래대로 출력
	revh.v의 원소를 역순으로, 횟수를 반대로 출력

 

예를 들면,

 

 

이외 행과 열 각각 움직이기, 중복 제거, 움직임 저장 등을 처리했다.

 

1. 격자판의 상태를 string으로 표현했기 때문에

2행을 움직인다면 s[4], s[5], s[6], s[7]을 

2열을 움직인다면 s[1], s[5], s[9], s[13]을 로테이션 했다.

또한 행은 오른쪽으로 한 칸 미는 시행을 4번, 열은 아래로 한 칸 미는 시행을 4번 해주어

원래의 상태로 돌아오게 해줬다.

 

2. 중복을 피하기 위해

저번 시행이 3번 행을 움직인 거였다면 이번 시행에서는 4번 행과 1~4번 열만 움직였고

저번 시행이 2번 열을 움직인 거였다면 이번 시행에서는 1~4번 행과 3, 4번 열만 움직였다.

행만 연속으로 움직이거나 열만 연속으로 움직이는 건 순서 관계가 없기 때문

1행 먼저 움직이고 3행 움직이나, 3행 먼저 움직이고 1행 움직이나 결과가 같다.

 

3. 움직인 방법은 그냥 세 자리 자연수로 저장했다.

1행을 3번 움직인 경우 113, 3열을 1번 움직인 경우 231과 같은 식으로

이게 가장 직관적이고 헷갈리지 않는 방법이었음..

 

 

#include <cstdio>
#include <vector>
#include <string>
#include <map>
using namespace std;

struct hist {
	vector<int> v;
};
map<string, hist> M[3];
int main() {
	int ans;
	string s(16, ' ');
	for (int i = 0; i < 16; ++i) scanf("%d", &ans), s[i] = ans - 1 + 'a';

	if (s == "abcdefghijklmnop") { printf("0"); return 0; }
	hist h, revh;
	M[0].insert({ s,h });
	M[1].insert({ "abcdefghijklmnop",h });

	char tmp;
	ans = 1;
	int A = 0, B = 1, C = 2;
	while (1) {
		for (auto it = M[A].begin(); it != M[A].end(); it++) {
			s = it->first; h = it->second;
			
			// 움직일 행, 열 범위 계산
			int i, j;
			if (h.v.empty()) i = j = 0;
			else if (h.v.back() < 200) i = ((h.v.back() - 100) / 10) << 2, j = 0;
			else i = 0, j = (h.v.back() - 200) / 10;
			
			// h.v에 원소 추가
			h.v.push_back(0);
			
			// 행 선택
			for ( ; i < 16; i += 4) {
				h.v.back() = 10 * ((i >> 2) + 11);
				for (int k = 0; k < 3; ++k) {
					// s, h.v.back() 변형
					h.v.back()++;
					tmp = s[i + 3], s[i + 3] = s[i + 2];
					s[i + 2] = s[i + 1], s[i + 1] = s[i], s[i] = tmp;
					
					// M[A]에 같은 원소 있는지 확인
					if (M[A].find(s) != M[A].end()) continue;

					// M[B]의 원소와 비교 
					auto tar = M[B].find(s);
					if (tar == M[B].end()) M[C].insert({ s,h });
					else {
						// 출력, 종료
						if (ans & 1) revh = tar->second;
						else revh = h, h = tar->second;

						printf("%d\n", ans);
						for (int idx = 0; idx < h.v.size(); ++idx) {
							int m = h.v[idx];
							printf("%d %d %d\n", m / 100, (m % 100) / 10, m % 10);
						}
						for (int idx = revh.v.size() - 1; idx >= 0; --idx) {
							int m = revh.v[idx];
							printf("%d %d %d\n", m / 100, (m % 100) / 10, 4 - (m % 10));
						}

						return 0;
					}
				}
				tmp = s[i + 3], s[i + 3] = s[i + 2];
				s[i + 2] = s[i + 1], s[i + 1] = s[i], s[i] = tmp;
			}
			// 열 선택
			for ( ; j < 4; ++j) {

				h.v.back() = 10 * (j + 21);
				for (int k = 0; k < 3; ++k) {
					h.v.back()++;
					tmp = s[j + 12], s[j + 12] = s[j + 8];
					s[j + 8] = s[j + 4], s[j + 4] = s[j], s[j] = tmp;

					if (M[A].find(s) != M[A].end()) continue;

					auto tar = M[B].find(s);
					if (tar == M[B].end()) M[C].insert({ s,h });
					else {
						if (ans & 1) revh = tar->second;
						else revh = h, h = tar->second;

						printf("%d\n", ans);
						for (int idx = 0; idx < h.v.size(); ++idx) {
							int m = h.v[idx];
							printf("%d %d %d\n", m / 100, (m % 100) / 10, m % 10);
						}
						for (int idx = revh.v.size() - 1; idx >= 0; --idx) {
							int m = revh.v[idx];
							printf("%d %d %d\n", m / 100, (m % 100) / 10, 4 - (m % 10));
						}

						return 0;
					}
				}
				tmp = s[j + 12], s[j + 12] = s[j + 8];
				s[j + 8] = s[j + 4], s[j + 4] = s[j], s[j] = tmp;
			}
		}
		M[A].clear();
		ans++; A++, A %= 3; B++, B %= 3; C++, C %= 3;
	}
}

 

 

이렇게 제출해 결국 맞았습니다!! 를 얻었지만 웬걸 엄청 적은 메모리만 쓴 풀이들이 있었으니

---

방법 2. DFS Backtracking Greedy(?)

 

 

현재 격자판과 목표 격자판에서 일치하지 않는 칸의 개수를 세 가장 적은 횟수로 움직이는 방법을 찾는다.

일치하지 않는 칸의 개수에 따라 움직일 최소 횟수는 정해져 있기 때문..

 

이번 움직임 후에

지금까지 움직인 횟수+앞으로 더 움직여야할 횟수≥이미 구해놓은 답 이라면,

이번 움직임은 굳이 하지 않는 게 좋다.

따라서 이번 움직임을 하기 전으로 돌아가 다른 움직임을 시도하면서 최소 횟수를 갱신한다.

 

시간은 비슷했지만 코드도 훨씬 간결하고, 메모리도 적게 사용한 풀이..

 

 

 

#include <cstdio>

int a[5][5], atmp[5], mov[9][3], mtmp[9][3], ANS = 8;
int extra[17] = { 0,5,5,5,1,5,5,2,2,5,3,5,3,4,5,5,4 };
void rotate_tile(int idx, int k) {
	if (idx < 4) {
		for (int i = 0; i < 4; i++) atmp[(i + k) % 4] = a[idx][i];
		for (int i = 0; i < 4; i++) a[idx][i] = atmp[i];
	}
	else {
		for (int i = 0; i < 4; i++) atmp[(i + k) % 4] = a[i][idx % 4];
		for (int i = 0; i < 4; i++) a[i][idx % 4] = atmp[i];
	}
}
void dfs(int cnt) {
	int diff = 0;
	for (int i = 0, num = 1; i < 4; i++) { // 틀린 갯수를 구함
		for (int j = 0; j < 4; j++, num++) if (a[i][j] != num) diff++;
	}

	// 지금이 정답
	if (!diff) { 
		ANS = cnt;
		for (int i = 0; i < cnt; i++) {
			mov[i][0] = mtmp[i][0]; mov[i][1] = mtmp[i][1]; mov[i][2] = mtmp[i][2];
		}
		return;
	}

	// 현재 ANS가 더 나음 => 굳이 X
	if (cnt + extra[diff] >= ANS) return;
	
	// 움직일만 하다
	for (int i = 0; i < 8; i++) {         // i행(0~3)/i열(4~7) 선택
		for (int k = 1; k < 4; k++) {     // k칸 이동
			if (i < 4) mtmp[cnt][0] = 1, mtmp[cnt][1] = i + 1, mtmp[cnt][2] = k;
			else mtmp[cnt][0] = 2, mtmp[cnt][1] = i - 3, mtmp[cnt][2] = k;

			rotate_tile(i, k); dfs(cnt + 1); rotate_tile(i, 4 - k);
		}
	}
}
int main() {
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) scanf("%d", &a[i][j]);
	}

	dfs(0);

	printf("%d\n", ANS);
	for (int i = 0; i < ANS; i++) printf("%d %d %d\n", mov[i][0], mov[i][1], mov[i][2]);
	
	return 0;
}

 

 

 

 

머리 터지고 내 풀이가 베스트가 아니라 슬펐지만

꼼꼼히 구현도 하고 생각도 많이 하고 새로운 풀이도 알게 된 시간..