BOJ 18139 : Rush Hour Puzzle (map)

삼성 B형 전체 링크

 

https://www.acmicpc.net/problem/18139

 

이후 설명 및 입/출력은 링크 참고

 

Hash, 2차원 배열 탐색을 이용하였던 Rush Hour Puzzle을 map으로 풀어보자.

 

문제의 핵심은 2차원 배열 탐색을 이용하여 hash한 값이 너무 커서, 다시 hash를 한 것이었다.

map을 이용하면 기존의 int hashMap[PRIME];으로 hash할 필요 없이 그대로 hash값을 저장할 수 있다.

typedef unsigned long long int ull;

map<ull, int> hashMap; /* key : 2차원 배열 hash 값, value : Level */

 

main에서 hashMap을 큰 값으로 초기화해줬으나, 이 코드는 더 이상 필요가 없다.

//for (int i = 0; i < PRIME; i++) hashMap[i] = 0x7fff0000;

 

DFS에서 MAP을 hashing 한 후, hashMap에 값을 Level을 저장하였다.

/* before */

void DFS(int L)
{
	if (MIN <= L) return;

	ull h = getHash(MAP);
	int p = h % PRIME;

	if (hashMap[p] > L) hashMap[p] = L;
	else return;
    
    ...
}

 

먼저 map.count(key)를 이용해, 값이 있는지 check한다. 해당 key에 대한 값이 없다면 0을 return한다.

key에 값이 없으므로 원래 했던 초기화를 하면 된다.

 

이후, 이 값과 L을 계속 갱신하면 된다.

/* after */

void DFS(int L)
{
	if (MIN <= L) return;

	ull h = getHash(MAP);

	if (hashMap.count(h) == 0) hashMap[h] = 0x7fff0000;

	if (hashMap[h] > L) hashMap[h] = L;
	else return;
    
    ...
}

 

map을 이용한 최종 코드는 아래와 같다.

#include <stdio.h>
#include <iostream>
#include <map>

using namespace std;

typedef unsigned long long int ull;

#define LEFT (0)
#define UP (1)
#define RIGHT (2)
#define DOWN (3)

#define MAP_SIZE (6)
#define PRIME (52967)

unsigned int MAP[10][10];

map<ull, int> hashMap;

typedef struct st2
{
	int r;
	int c;
	int dir;
	int length;
}CAR;

CAR car[11];
int ccnt;

void input()
{
	/* 주변을 벽으로 만든다. */
	for (int r = 0; r <= MAP_SIZE + 1; r++)
		for (int c = 0; c <= MAP_SIZE + 1; c++)
			MAP[r][c] = -1;

	/* MAP 입력 */
	for (int r = 1; r <= MAP_SIZE; r++)
		for (int c = 1; c <= MAP_SIZE; c++)
			scanf("%d", &MAP[r][c]);

	for (int r = 1; r <= MAP_SIZE; r++)
	{
		for (int c = 1; c <= MAP_SIZE; c++)
		{
			if (MAP[r][c])
			{
				int carNum = MAP[r][c];

				/* hash를 위해 1로 변경 */
				MAP[r][c] = 1;

				if (car[carNum].length != 0) continue; /* 이미 입력 받은 차라면 continue */

													   /* 자동차 정보 저장 */

				ccnt++;
				if (MAP[r][c + 1] == carNum) /* 가로로 놓인 차*/
				{
					car[carNum].r = r;
					car[carNum].c = c;
					car[carNum].dir = LEFT; /* 가로 표시 */

					if (MAP[r][c + 2] == carNum) car[carNum].length = 3;
					else car[carNum].length = 2;
				}
				else
				{
					car[carNum].r = r;
					car[carNum].c = c;
					car[carNum].dir = UP; /* 세로 표시 */

					if (MAP[r + 2][c] == carNum) car[carNum].length = 3;
					else car[carNum].length = 2;
				}
			}
		}
	}
}

void output()
{
	int tmpMAP[10][10] = { 0 };

	for (int i = 1; i <= 10; i++)
	{
		int length = car[i].length;

		for (int k = 0; k < length; k++)
		{
			int r, c;

			if (car[i].dir == LEFT)
			{
				r = car[i].r;
				c = car[i].c + k;

				tmpMAP[r][c] = i;
			}
			else
			{
				r = car[i].r + k;
				c = car[i].c;

				tmpMAP[r][c] = i;
			}
		}
	}

	for (int r = 1; r <= MAP_SIZE; r++)
	{
		for (int c = 1; c <= MAP_SIZE; c++)
			printf("%d ", tmpMAP[r][c]);
		putchar('\n');
	}
	putchar('\n');
}

ull getHash(unsigned int MAP[10][10])
{
	ull hash = 0;
	ull count = 0;

	for (int r = 1; r <= MAP_SIZE; r++)
		for (int c = 1; c <= MAP_SIZE; c++)
			hash |= (((ull)MAP[r][c]) << count++);

	return hash;
}

/* 순서대로 왼쪽, 위, 오른쪽, 아래 */
int dr[] = { 0, -1, 0, 1 };
int dc[] = { -1, 0, 1, 0 };

int isMoveRight(CAR car, unsigned MAP[][10])
{
	if (MAP[car.r + dr[RIGHT]][car.c + car.length - 1 + dc[RIGHT]] != 0) return 0;

	int length = car.length;

	for (int i = length - 1; i >= 0; i--)
	{
		int nr, nc;

		nr = car.r + dr[RIGHT];
		nc = car.c + i + dc[RIGHT];

		MAP[car.r][car.c + i] = 0;
		MAP[nr][nc] = 1;
	}

	return 1;
}

int isMoveLeft(CAR car, unsigned MAP[][10])
{
	if (MAP[car.r + dr[LEFT]][car.c + dc[LEFT]] != 0) return 0;

	int length = car.length;

	for (int i = 0; i < length; i++)
	{
		int nr, nc;

		nr = car.r + dr[LEFT];
		nc = car.c + i + dc[LEFT];

		MAP[car.r][car.c + i] = 0;
		MAP[nr][nc] = 1;
	}

	return 1;
}

int isMoveUp(CAR car, unsigned MAP[][10])
{
	if (MAP[car.r + dr[UP]][car.c + dc[UP]] != 0) return 0;

	int length = car.length;

	for (int i = 0; i < length; i++)
	{
		int nr, nc;

		nr = car.r + i + dr[UP];
		nc = car.c + dc[UP];

		MAP[car.r + i][car.c] = 0;
		MAP[nr][nc] = 1;
	}

	return 1;
}

int isMoveDown(CAR car, unsigned MAP[][10])
{
	if (MAP[car.r + car.length - 1 + dr[DOWN]][car.c + dc[DOWN]] != 0) return 0;

	int length = car.length;

	for (int i = length - 1; i >= 0; i--)
	{
		int nr, nc;

		nr = car.r + i + dr[DOWN];
		nc = car.c + dc[DOWN];

		MAP[car.r + i][car.c] = 0;
		MAP[nr][nc] = 1;
	}

	return 1;
}

int MIN = 0x7fff0000;
void DFS(int L)
{
	if (MIN <= L) return;

	ull h = getHash(MAP);

	if (hashMap.count(h) == 0) hashMap[h] = 0x7fff0000;

	if (hashMap[h] > L) hashMap[h] = L;
	else return;

	if (car[1].c == 5)
	{
		if (L < MIN) MIN = L;

		return;
	}

	if (L > 7) return;

	for (int i = 1; i <= ccnt; i++)
	{
		if (car[i].dir == LEFT) /* 가로 차인 경우 */
		{
			if (isMoveRight(car[i], MAP))
			{
				car[i].c++;
				DFS(L + 1);

				isMoveLeft(car[i], MAP);
				car[i].c--;
			}

			if (isMoveLeft(car[i], MAP))
			{
				car[i].c--;
				DFS(L + 1);

				isMoveRight(car[i], MAP);
				car[i].c++;
			}
		}
		else /* 세로 차인 경우 */
		{
			if (isMoveUp(car[i], MAP))
			{
				car[i].r--;
				DFS(L + 1);

				isMoveDown(car[i], MAP);
				car[i].r++;
			}

			if (isMoveDown(car[i], MAP))
			{
				car[i].r++;
				DFS(L + 1);

				isMoveUp(car[i], MAP);
				car[i].r--;
			}
		}
	}
}

void printbinary(ull a)
{
	ull mask = (ull)1 << 63;
	for (int i = 0; i < 64; i++)
	{
		printf("%d", (a & mask) == mask);
		mask >>= 1;
		if (i % 4 == 3) printf(" ");
	}
	putchar('\n');
}

int main(void)
{
	input();

	//for (int i = 0; i < PRIME; i++) hashMap[i] = 0x7fff0000;

	DFS(0);

	if (MIN == 0x7fff0000) printf("-1\n");
	else printf("%d\n", MIN + 2);

	return 0;
}

---

이 문제에서 운 좋게 hash 충돌이 일어나지 않았기 때문에

hashMap[PRIME]으로 풀 경우 O(1)만에 접근 가능하지만, map의 경우는 O(logN)이 걸린다.

 

따라서 실제 B형에서 map으로 탐색할 때, query가 많다면 hash를 고려해보는 것이 좋다.