반응형
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를 고려해보는 것이 좋다.
반응형
'알고리즘 > [PRO] 삼성 B형 STL 연습' 카테고리의 다른 글
BOJ 11286 : 절댓값 힙 (priority_queue, compare) (0) | 2021.06.21 |
---|---|
BOJ 1927 : 최소 힙 (priority_queue, compare) (0) | 2021.06.19 |
BOJ 11279 : 최대 힙 (priority_queue) (0) | 2021.06.19 |
BOJ 1764 : 듣보잡 (vector, sort) (4) | 2021.06.18 |
BOJ 1707 : 이분 그래프 (vector) (1) | 2021.06.17 |
댓글