참고
- 해시 응용 - Rush Hour Puzzle (2차원 배열 탐색 응용)
내용을 번역해서 요약하면 아래와 같다.
1) 6 x 6 board에서 자동차가 최대 10개 존재한다.
2) 자동차는 1칸씩 움직이며, 길이가 2 또는 3이다.
3) 1번 자동차가 exit로 탈출해야 한다.
4) exit는 항상 3번째 줄의 오른쪽 끝이다. 따라서 1번 자동차는 항상 3번째 줄에 가로로 존재한다.
5) 최대 10칸까지 움직인다. 그 이상 움직여도 1번 자동차가 exit로 탈출 못하면 -1을 출력한다.
아래의 조건은 문제를 풀면서 알게 된 조건이다.
이 조건은 tc가 부족하거나, 문제를 복구하는 과정에서 빠졌을거라고 예상된다.
6) 1번 자동차의 길이는 항상 2다.
7) 자동차는 순서대로 존재한다. (1, 2, 5, 6, 7로 존재하지 않고 1, 2, 3, 4, 5 순서대로 존재한다.)
6 x 6 을 hashing 하여 문제를 해결한다.
unsigned long long int가 64bit이므로 36칸의 2차원 배열을 한 번에 저장할 수 있다.
(2차원 배열 탐색에서 마지막 방법을 이용하였다.)
여기에서 자동차가 1 ~ 10으로 주어지기 때문에, 자동차는 따로 배열로 관리하고,
MAP에서 존재하는 자동차는 모두 1로 변경한다.
hashing을 하는 이유는 DFS로 자동차를 움직였을 때, 다시 그 위치에 왔었는지 체크하기 위해서 이다.
예전에 한 번 도착했던, 자동차의 배치라면, 더 이상 DFS를 진행할 필요가 없기 때문이다.
문제를 풀기 전에 아래의 예시가 답이 6이 되는 것을 확인해보자. (예제 입력 2)
(1) 6번 차를 왼쪽으로 옮긴다.
(2) 7번 차를 위로 옮긴다.
(3) ~ (6) 1번 차를 오른쪽으로 4칸 옮긴다.
1번 차가 완전히 exit로 나갈 때 움직인 횟수를 출력해야 한다. 예제 입력 2의 답이 6이기 때문이다.
여기서 첫 번째 최적화를 정할 수 있다.
1번 차의 왼쪽 부분이 r = 3, c = 5에 최소 몇 번만에 도착하는지 구하면 된다.
따라서 최대 10번 움직여 볼 필요 없이 최대 8번 움직이고 답을 출력할 때는 +2를 하면 된다.
이제 input을 구현해보자.
경계 조건을 체크하는 것보다 주변을 벽으로 만드는 것이 자동차가 움직일 수 있는 지 체크하기 좋다.
따라서 먼저 벽을 8 x 8 MAP에 벽을 만든다. 그리고 MAP의 입력을 (1, 1)부터 받는다.
이제 MAP에 자동차가 있는 경우, 자동차 구조체에 자동차의 정보를 저장한다.
자동차가 세로라면 가장 윗부분의 (r, c)를 저장하고, 가로라면 가장 왼쪽부분의 (r, c)를 저장한다.
세로인지 가로인지는 MAP[r][c + 1]에 같은 번호가 있는 지 체크해서 판단한다.
그리고 한칸 더 체크해서 같은 번호가 있다면, 길이를 3, 없다면 길이를 2로 저장한다.
그리고 dir은 가로는 LEFT(0), 세로는 UP(1)로 저장한다.
마지막으로 hash를 위해 MAP[r][c] = 1로 변경한다.
#define LEFT (0)
#define UP (1)
#define RIGHT (2)
#define DOWN (3)
#define MAP_SIZE (6)
unsigned int MAP[10][10];
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;
}
}
}
}
}
MAP에 있는 자동차를 모두 1로 표시하였으므로, getHash 함수를 구현해보자.
(1, 1)은 비트의 0번에, (1, 2)는 비트의 1번에, ..., (6, 6)은 비트의 35번에 저장한다.
typedef unsigned long long int ull;
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;
}
아래의 예시는 오른쪽 그림처럼 변경되고 hash값은 511304858이 된다.
(0000 0000 0000 0000 0000 0000 0000 0000 0001 1110 0111 1001 1110 0100 1001 1010)
실제로 확인하고 싶다면, printbinary 함수를 이용해 비트를 출력해보자.
typedef unsigned long long int ull;
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();
printf("hash : %llu\n", getHash(MAP));
printbinary(getHash(MAP));
return 0;
}
6 x 6의 hash의 경우 MAP이 모두 1일 때, 가장 큰 값으로 68719476735를 가진다.
이 숫자는 메모리로 잡기에는 너무 큰 값이다.
그러나, MAP이 모두 1이 될 수 없고 자동차의 움직임이 매우 제한되어있기 때문에, 다시 hashing이 필요하다.
이 값을 다시 적절한 소수로 나눈 나머지로 다시 hashing하면 된다.
여기에서는 50000보다 약간 큰 소수인 52967을 사용하였다. 소수를 찾는 방법은 링크를 참고하자.
hash에 의해 충돌이 발생하는 경우에 대해서는 마지막에 따로 설명하겠다.
최종적으로 위의 예제는 68719476735 % 52967 = 14407로 해싱된다.
hashMap에는 지도까지 걸린 횟수 Level을 저장한다. 따라서 hashMap[14407]은 0이다.
DFS가 hashMap을 갱신할 때,
hashMap에 도달하는 Level의 최솟값을 저장하기 때문에, 초기에 적당히 큰 값으로 초기화 해둔다.
#define PRIME (52967)
int hashMap[PRIME];
int main(void)
{
input();
/* hashMap의 초기화 */
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;
}이제 DFS를 만들어보자.
DFS의 종료 조건은 아래와 같다.
1) hashMap을 이용하여 자동차를 움직여서 변경된 MAP의 depth를 알게 된다.
따라서, hashMap <= L인 경우는 이미 이전 Level에서 도착한 경우이므로 DFS를 종료한다.
2) 1번 자동차의 column = 5면 종료한다. 이 경우는 rush hour 퍼즐을 푼 경우이므로 최소 MIN을 L로 갱신한다.
3) L > 7, 즉, L = 8인 경우는 게임 실패 이므로 종료한다.
4) (+최적화) 2번에서 갱신된 MIN보다 L이 큰 경우는 더 찾을 필요가 없으므로 종료한다.
int MIN = 0x7fff0000;
void DFS(int L)
{
if (MIN <= L) return; /* 4) 경우 */
ull h = getHash(MAP);
int p = h % PRIME;
if (hashMap[p] > L) hashMap[p] = L;
else return; /* 1) 경우 */
if (car[1].c == 5) /* 2) 경우 */
{
if (L < MIN) MIN = L;
return;
}
if (L > 7) return; /* 3) 경우 */
...
}
ull h = getHash(MAP)은 MAP을 unsigned long long int 형으로 hashing한다.
int p = h % PRIME로 한번 더 작게 hashing한다.
그러면 hashMap[p]를 확인했을 때, 현재 MAP이 몇 번만에 도착한 MAP인지 알 수 있다.
이제 DFS를 실행해보자.
DFS는 1번 부터 ccnt(CAR의 개수) 까지 차를 직접 움직여야 한다.
가로의 차라면 오른쪽이나, 왼쪽으로 움직이고, 세로의 차라면 위나 아래로 움직여 본다.
움직일 수 있는 경우, MAP이 변경되고 다음 Level의 DFS로 넘어간다.
가로로 놓인 차의 경우는 아래와 같이 구현된다.
void DFS(int L)
{
/* 종료 조건 1) ~ 4) */
for (int i = 1; i <= ccnt; i++) /* 모든 자동차 for loop */
{
if (car[i].dir == LEFT) /* 가로 차인 경우 */
{
if (isMoveRight(car[i], MAP)) /* 오른쪽으로 움직일 수 있는가 ? */
{
car[i].c++; /* 해당 차의 좌표 갱신, 오른쪽 이동 */
DFS(L + 1);
isMoveLeft(car[i], MAP); /* DFS 종료 후 왼쪽 이동하여 MAP 복구 */
car[i].c--; /* 해당 차의 좌표 갱신, 왼쪽 이동 */
}
if (isMoveLeft(car[i], MAP)) /* 왼쪽으로 움직일 수 있는가 ? */
{ ... }
}
else /* 세로 차인 경우 */
{ ... }
}
}
먼저 오른쪽으로 갈 수 있는지 판단하는 함수 isMoveRight를 실행한다.
isMoveRight는 움직일 수 있다면 1을 return하고 MAP을 변경한다.
MAP만 변경하면 안되므로, 자동차의 좌표, 가로인 경우이므로 c를 증가시킨다.
그리고 다음 DFS로 넘어간다.
DFS가 종료되면 isMoveLeft를 실행해서 MAP을 원래대로 복구시키고, 자동차의 좌표도 원래대로 복구시킨다.
isMoveRight는 아래와 같이 구현된다.
자동차를 움직이기 위해, dr, dc 배열을 선언해두고, 0 ~ 3에 맞는 값을 LEFT/UP/RIGHT/DOWN으로 define 해둔다.
자동차의 길이를 고려하여 자동차의 옆 칸이 0인지 체크하고, 0이 아니라면 0을 return해서 MAP을 보존한다.
자동차의 옆이 0인 경우는 자동차의 길이를 고려하여 한 칸씩 움직인다.
오른쪽으로 움직이므로, 자동차의 좌표 + length - 1 부터 자동차를 1칸씩 움직인다.
이런 함수를 구현할 때는 MAP을 출력하는 함수를 만들어서 제대로 움직이는지 확인을 꼭 해야 한다.
#define LEFT (0)
#define UP (1)
#define RIGHT (2)
#define DOWN (3)
/* 순서대로 왼쪽, 위, 오른쪽, 아래 */
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;
}
left / up / down은 최종 코드를 참고하자.
모든 자동차에 대해 움직였으니 car[1].c == 5인 경우에 최소 L이 갱신되었을 것이다.
따라서 MIN이 갱신되지 않으면 -1을 출력하고, 갱신되었다면 2를 더해서 출력한다.
int main(void)
{
...
DFS(0);
if (MIN == 0x7fff0000) printf("-1\n");
else printf("%d\n", MIN + 2);
return 0;
}
최종 코드는 아래와 같다.
#include <stdio.h>
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];
int hashMap[PRIME];
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);
int p = h % PRIME;
if (hashMap[p] > L) hashMap[p] = 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;
}
DFS를 할 때, moveLeft보다 moveRight를 먼저해주었다.
이 것은 1번 자동차가 moveRight를 먼저 해보는 것이 더 최적화에 도움이 되기 때문이다.
위의 코드는 hash 충돌에 대해서는 고려하지 않았다.
1) hash의 값은 매우 크지만, 자동차의 움직임이 많이 제한되어 있기 때문에, 값의 충돌이 거의 없는 것 같다.
2) PRIME으로 나누면 충돌이 덜 하다. 이것은 기본 해시 테이블 문제에서도 이용하는 기법이다.
실제 처음에는 충돌이 발생하는 경우를 고려하여 코드를 구현하였다.
그러나 충돌이 실제 발생하는지 체크해본 결과, 충돌이 없어서 현재의 코드로 변경하였다.
특히, PRIME 52967을 (소수가 아닌) 12345로 define하여도 충돌이 발생하지 않았다.
만약 tc에서 충돌이 일어나는 경우면 아래와 같이 보완할 수 있다.
- 더 큰 소수로 나머지 연산을 한다.
- 그래도 충돌이 발생한다면 hashMap[PRIME][50] 정도로 넉넉하게 잡아서 충돌 여부를 검색한 후, hash를 추가한다.
당연히 이 때는 hashMap의 type에 실제 hash값을 기억하도록 구조체 형태로 바꿔야 한다.
'알고리즘 > [PRO] 삼성 SW 역량 테스트 B형' 카테고리의 다른 글
| BOJ 7662 : 이중 우선순위 큐 (1) | 2021.03.24 |
|---|---|
| BOJ 20920 : 영단어 암기는 괴로워 (우선순위 큐 갱신 + Hash Table) (0) | 2021.03.21 |
| Indexed Priority Queue - 우선순위 큐의 임의 원소 삭제 (2) : 최적화 (0) | 2021.03.13 |
| Indexed Priority Queue - 우선순위 큐의 임의 원소 삭제 (1) | 2021.03.13 |
| 해시 응용 : 2차원 배열 탐색 (5) | 2021.03.09 |
댓글