https://algospot.com/judge/problem/read/BOGGLE
algospot.com :: BOGGLE
보글 게임 문제 정보 문제 보글(Boggle) 게임은 그림 (a)와 같은 5x5 크기의 알파벳 격자인 게임판의 한 글자에서 시작해서 펜을 움직이면서 만나는 글자를 그 순서대로 나열하여 만들어지는 영어
algospot.com
문제: 시간제한 1초, 메모리제한 65536kb
보글(Boggle) 게임은 그림 (a)와 같은 5x5 크기의 알파벳 격자인
게임판의 한 글자에서 시작해서 펜을 움직이면서 만나는 글자를 그 순서대로 나열하여 만들어지는 영어 단어를 찾아내는 게임입니다. 펜은 상하좌우, 혹은 대각선으로 인접한 칸으로 이동할 수 있으며 글자를 건너뛸 수는 없습니다. 지나간 글자를 다시 지나가는 것은 가능하지만, 펜을 이동하지않고 같은 글자를 여러번 쓸 수는 없습니다.
예를 들어 그림의 (b), (c), (d)는 각각 (a)의 격자에서 PRETTY, GIRL, REPEAT을 찾아낸 결과를 보여줍니다.
보글 게임판과 알고 있는 단어들의 목록이 주어질 때, 보글 게임판에서 각 단어를 찾을 수 있는지 여부를 출력하는 프로그램을 작성하세요.
주의: 알고리즘 문제 해결 전략 6장을 읽고 이 문제를 푸시려는 분들은 주의하세요. 6장의 예제 코드는 이 문제를 풀기에는 너무 느립니다. 6장의 뒷부분과 8장을 참조하세요.
입력
입력의 첫 줄에는 테스트 케이스의 수 C(C <= 50)가 주어집니다. 각 테스트 케이스의 첫 줄에는 각 5줄에 5글자로 보글 게임판이 주어집니다. 게임판의 모든 칸은 알파벳 대문자입니다.
그 다음 줄에는 우리가 알고 있는 단어의 수 N(1 <= N <= 10)이 주어집니다. 그 후 N줄에는 한 줄에 하나씩 우리가 알고 있는 단어들이 주어집니다. 각 단어는 알파벳 대문자 1글자 이상 10글자 이하로 구성됩니다.
출력
각 테스트 케이스마다 N줄을 출력합니다. 각 줄에는 알고 있는 단어를 입력에 주어진 순서대로 출력하고, 해당 단어를 찾을 수 있을 경우 YES, 아닐 경우 NO를 출력합니다.
예제 입력
1
URLPM
XPRET
GIAET
XTNZY
XOQRS
6
PRETTY
GIRL
REPEAT
KARA
PANDORA
GIAZAPX
예제 출력
PRETTY YES
GIRL YES
REPEAT YES
KARA NO
PANDORA NO
GIAZAPX YES- tc 50
- 게임판 5 * 5
- 단어 수 10
- 단어 글자수 10
- 게임판의 한 글자에서 시작하여, 입력 단어를 찾는 한붓 그리기(상하좌우, 대각선 인접 칸으로 이동 가능, 지나간 글자 다시 지나가기 가능)
풀이1: 깊이우선탐색
게임판 문자로 이동한다.
입력 단어 문자가 없으면 다음 단어로 이동한다.
입력 단어 문자가 있으면 인접 칸으로 이동한다.
입력 단어 문자가 완성됐으면 다음 단어로 이동한다.
입력 단어를 찾는데, 입력 단어 문자로 쪼개서 풀어야 한다.
재귀 호출을 사용해서 게임판을 전체 탐색하도록 해보자. 재귀 호출에 전체 탐색이므로 깊이우선탐색이 되겠구나.
(그리고 지나간 칸을 다시 돌아오는 것이 가능하기 때문에, 지나간 칸을 표시할 필요는 없겠구나)
위와 같이 구현한다면, worst case의 시간 복잡도는 얼마나 될까?
worst case는 입력 단어가 10개이고 단어 글자수가 10이고, 게임판에서 어떤 단어도 완성하지 못하는 경우이다.
예제 worst case는 다음과 같다. 이는 tc 1개, 입력 단어 1개, 글자 수 10개이다.
1
AAAAA
AAAAA
AAAAA
AAAAA
AAAAA
1
AAAAAAAAAB
단어 글자수 10인 단어 1개의 시간복잡도는 25(게임판 크기) * 8(인접 칸 이동방향)^10(단어 글자수) 이다. 이는 25 * 10^9으로 25초 정도의 시간이다. 단어 1개로 이미 25초가 걸린다. 총 50(tc) * 10(단어수) * 25 * 10^9(단어 1개)는 12500초가 걸린다.
단어 1개에 대해서 수행시간은 얼마나 걸리는 지 확인해보자.
4초 정도 소요됐다. (25초는 10*9을 1초로 worst하게 계산했다. 그러나 내 PC의 CPU에서는 0.2 ~ 0.55초로 계산된다.)
#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <cassert>
#include <chrono>
#define DEBUG (0)
#if (1 == DEBUG)
#define DEBUG_PRINT printf
#else
#define DEBUG_PRINT
#endif
using namespace std;
char map[5][5];
char str[10][10 + 1];
int strLen[10];
bool isDone[10];
const int dx[8] = { 0, 0, -1, 1, -1, -1, 1, 1 };
const int dy[8] = { -1, 1, 0, 0, 1, -1, 1, -1 };
const char* yes = "YES";
const char* no = "NO";
bool isGoToNext(int r, int c, int strId, int charId);
void dps(int r, int c, int strId, int charId);
int main()
{
auto start = chrono::high_resolution_clock::now();
setbuf(stdout, NULL);
freopen("input.txt", "r", stdin);
int tc;
scanf("%d", &tc);
for (int t = 0; t < tc; t++)
{
// input
getchar();
for (int i = 0; i < 5; i++)
{
for (int j = 0; j < 5; j++)
{
scanf("%c", &map[i][j]);
}
getchar();
}
int strCnt;
scanf("%d", &strCnt);
for (int i = 0; i < strCnt; i++)
{
scanf("%s", str[i]);
strLen[i] = strlen(str[i]);
}
memset(isDone, 0, sizeof(isDone));
// solve
for (int i = 0; i < 5; i++)
{
for (int j = 0; j < 5; j++)
{
DEBUG_PRINT(">> 1. (%d, %d), char = %c\n", i, j, map[i][j]);
for (int s = 0; s < strCnt; s++)
{
DEBUG_PRINT(">> 2. string[%d] = %s\n", s, str[s]);
if (isDone[s]) continue;
if (map[i][j] == str[s][0])
{
dps(i, j, s, 0);
}
}
}
}
for (int i = 0; i < strCnt; i++)
{
printf("%s", str[i]);
char temp[4] = { 0 };
if (isDone[i])
{
printf(" %s\n", yes);
}
else
{
printf(" %s\n", no);
}
}
}
auto end = chrono::high_resolution_clock::now();
auto duration = chrono::duration_cast<chrono::milliseconds>(end - start);
cout << "Execution time: " << duration.count() << " milliseconds" << endl;
return 0;
}
bool isGoToNext(int r, int c, int strId, int charId)
{
return (r >= 0) && (r < 5) && (c >=0) && (c < 5)
&& (map[r][c] == str[strId][charId]) && (0 == isDone[strId]);
}
void dps(int r, int c, int strId, int charId)
{
DEBUG_PRINT(">> 3. dps: (%d, %d), map = %c, str[%d][%d] = %c\n", r, c, map[r][c], strId, charId, str[strId][charId]);
if (strLen[strId] == charId+1)
{
DEBUG_PRINT(">> 4. done\n");
isDone[strId] = 1;
}
else
{
for (int i = 0; i < 8; i++)
{
int nextRow = r + dx[i];
int nextCol = c + dy[i];
int nextId = charId + 1;
if (isGoToNext(nextRow, nextCol, strId, nextId))
{
dps(nextRow, nextCol, strId, nextId);
}
}
}
}
단어 1개의 시간 복잡도가 8^10인데, 여기에는 동일 루트에 대한 중복 연산이 포함되어 있다.
풀이2: memoization
풀이1에서 중복 연산을 줄일 수 있는 방법은 무엇이 있을까?
검색을 해보니, 메모이제이션을 사용해야할 거 같다.
Memoization is used to optimize recursive algorithms by storing the results of expensive function calls and reusing them when the same inputs occur again. This prevents redundant computations and improves efficiency, especially in problems involving overlapping subproblems, such as:
- Dynamic programming: Problems like Fibonacci sequence, knapsack, or grid paths.
- Search algorithms: Depth-first search in graphs, such as pathfinding or word search problems.
- Optimization problems: Minimizing/maximizing results over multiple states.
풀이1에서는 게임판의 좌표에서 임의의 문자에 대해 중복으로 단어 탐색 루트를 확인하고 있다.
그래서, worst case(특정 단어가 존재하지 않는다고 결정하는 데)에서 8(이동방향 수)^10(단어 길이)만큼의 연산이 필요했다.
단어 탐색 루트가 왜 중복되고 있을까? 좌표에서 단어의 n번째 문자를 중복으로 탐색하고 있기 때문이다.
그렇다면, 좌표에서 단어의 n번째 문자를 1번만 탐색하도록, 메모이제이션을 사용하면 되지 않을까?
그렇게 하면, worst case에서 10(단어 길이) 만큼의 연산으로 가능하다.
8^10이 10으로 줄어들게 된다!!!
#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
#include <stdio.h>
#include <iostream>
#include <cstring>
#if (1 == DEBUG)
#include <cassert>
#include <chrono>
#endif
#define TIME (0)
#define DEBUG (0)
#if (1 == DEBUG)
#define DEBUG_PRINT printf
#else
#define DEBUG_PRINT
#endif
using namespace std;
char map[5][5];
char str[10][10 + 1];
int strLen[10];
bool isDone[10];
const int dx[8] = { 0, 0, -1, 1, -1, -1, 1, 1 };
const int dy[8] = { -1, 1, 0, 0, 1, -1, 1, -1 };
const char* yes = "YES";
const char* no = "NO";
int memo[5][5][10];
bool dps(int r, int c, int strId, int charId);
int main()
{
#if (1 == TIME)
auto start = chrono::high_resolution_clock::now();
#endif
setbuf(stdout, NULL);
freopen("input.txt", "r", stdin);
int tc;
scanf("%d", &tc);
for (int t = 0; t < tc; t++)
{
// input
getchar();
for (int i = 0; i < 5; i++)
{
for (int j = 0; j < 5; j++)
{
scanf("%c", &map[i][j]);
}
getchar();
}
int strCnt;
scanf("%d", &strCnt);
for (int i = 0; i < strCnt; i++)
{
scanf("%s", str[i]);
strLen[i] = strlen(str[i]);
}
memset(isDone, 0, sizeof(isDone));
// solve
for (int i = 0; i < 5; i++)
{
for (int j = 0; j < 5; j++)
{
DEBUG_PRINT("\n>> 1. (%d, %d), char = %c\n", i, j, map[i][j]);
for (int s = 0; s < strCnt; s++)
{
memset(memo, -1, sizeof(memo));
DEBUG_PRINT(">> 2. string[%d] = %s\n", s, str[s]);
if (isDone[s]) continue;
if (dps(i, j, s, 0))
{
isDone[s] = true;
}
}
}
}
for (int i = 0; i < strCnt; i++)
{
printf("%s", str[i]);
char temp[4] = { 0 };
if (isDone[i])
{
printf(" %s\n", yes);
}
else
{
printf(" %s\n", no);
}
}
}
#if (1 == TIME)
auto end = chrono::high_resolution_clock::now();
auto duration = chrono::duration_cast<chrono::milliseconds>(end - start);
cout << "Execution time: " << duration.count() << " milliseconds" << endl;
#endif
return 0;
}
bool dps(int r, int c, int strId, int charId)
{
if ((r < 0) || (r >= 5) || (c < 0) || (c >= 5)) return false;
if (-1 != memo[r][c][charId]) return memo[r][c][charId];
if (map[r][c] != str[strId][charId]) return false;
if (strLen[strId] == charId + 1)
{
DEBUG_PRINT(">> 4. dps: (%d, %d), map = %c, str[%d][%d] = %c\n"
, r, c, map[r][c], strId, charId, str[strId][charId]);
return true;
}
DEBUG_PRINT(">> 3. dps: (%d, %d), map = %c, str[%d][%d] = %c\n"
, r, c, map[r][c], strId, charId, str[strId][charId]);
for (int i = 0; i < 8; i++)
{
int nextRow = r + dx[i];
int nextCol = c + dy[i];
int nextId = charId + 1;
if (dps(nextRow, nextCol, strId, nextId))
{
memo[nextRow][nextCol][nextId] = 1;
return true;
}
}
memo[r][c][charId] = 0;
return false;
}
정리
동일한 입력으로 인해 중복 계산이 발생하는 재귀 알고리즘에서, 메모이제이션은 각각의 고유한 계산 결과를 저장하여 재계산을 방지할 수 있다.
'컴퓨터 > Problem Solving' 카테고리의 다른 글
| [ALGOSPOT] 록 페스티벌 (4) | 2024.10.01 |
|---|