controlpro
[알고리즘 문제해결 전략] 보글게임 본문
친구의 추천으로 <프로그래밍 대회에서 배우는 알고리즘 문제해결 전략> 이라는 책을 샀다. 책 내용을 전부다 정리 할 수는 없겠지만 이 책을 통해 많이 배우자!
문제
보글(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를 출력합니다. https://algospot.com/judge/problem/read/BOGGLE
algospot.com :: BOGGLE
보글 게임 문제 정보 문제 보글(Boggle) 게임은 그림 (a)와 같은 5x5 크기의 알파벳 격자인 게임판의 한 글자에서 시작해서 펜을 움직이면서 만나는 글자를 그 순서대로 나열하여 만들어지는 영어
algospot.com
문제는 다음과 같고, 나는 아직 6장을 하고 있으니까 저 algospot기준으로 하지 않고 다 돌아가기만 하도록 만들어 봤다.
일단 이 문제를 해결하기 위해서는 재귀함수를 사용하라고 나와 있는데, 특정 조건이 계속해서 반복해서 나오면 for을 계속해서 사용하는 것보다, 재귀함수를 이용해서 푸는 것이 좋다고 한다.
재귀함수를 사용하기 위해서는 기저 조건 즉 loop를 탈출하는 조건이 가장 중요하다.(이거 안해서 계속 false 났음 ㅠ)
1. 문제 분할 하기
일단 모든 경우를 체크하면서 map을 탐색하기 때문에 입력한 string의 첫 글자가 시작되는 함수를 하나 만들어야하고 그 다음은 다음 idx의 글자가 주변 8칸에 있는지 확인을 해야한다 .
여기서 다음 idx의 글자가 주변 8칸에 있는지 확인하는 과정이 계속해서 반복되니까 이 부분을 재귀함수로 구현하면 될거 같다.
2. 기저조건 만들기
- (x ,y) 좌표가 문제에서 주어진 5 by 5를 넘어갔을 때
- 원하는 글자가 한 글자일 경우 바로 성공
- 글자를 다 찾은 경우
3. Coding
코딩할때 c로 할까 C++로 할까 고민하다가 C++로 짜서 중간중간 C코드의 흠적이 보인다 .. ㅎ 이해좀
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
char map[5][5] = {0,};
char word[10];
int dy[8] = { -1,-1,-1,1,1,1,0,0 };
int dx[8] = { -1,0,1,-1,0,1,-1,0 };
int nextFind(int by, int bx, int idx , char *word) {
// Rangecheck 기저함수를 잘체그하자
int nextidx = idx + 1;
if (by < 0 || by >= 5 || bx < 0 || bx >= 5) {
return 0;
}
if (nextidx >= strlen(word)) {
return 1;
}
if (strlen(word) == 1)
return 1;
for (int direction = 0; direction < 8; direction++) {
int nextY = by + dy[direction];
int nextX = bx + dx[direction];
if (map[nextY][nextX] == word[nextidx]) {
;
if (nextFind(nextY, nextX, nextidx , word))
return 1;
}
}
return 0;
}
int startWord(char *word) {
int bx, by;
for (by = 0; by < 5; by++) {
for (bx = 0; bx < 5; bx++) {
if (map[by][bx] = word[0]) {
if (nextFind(by, bx, 0 , word)) {
return 1;
}
}
}
}
return 0;
}
int main(void) {
int testcase , tc;
int i, j;
int num;
printf("input testcase : ");
scanf_s("%d", &testcase);
for (tc = 0; tc < testcase; tc++) {
for (i = 0; i < 5; i++) {
for (j = 0; j < 5; j++) {
printf("input %d by %d : ", i+1, j+1);
cin >> map[i][j];
}
}
printf("input num :");
scanf_s("%d", &num);
for (i = 0; i < num; i++) {
cin >> word;
if (startWord(word))
printf("%s : YES\n", word);
else
printf("%s : NO\n", word);
}
}
}
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
char map[5][5] = {0,};
char word[10];
int dy[8] = { -1,-1,-1,1,1,1,0,0 };
int dx[8] = { -1,0,1,-1,0,1,-1,0 };
int nextFind(int by, int bx, int idx , char *word) {
// Rangecheck 기저함수를 잘체그하자
int nextidx = idx + 1;
if (by < 0 || by >= 5 || bx < 0 || bx >= 5) {
return 0;
}
if (nextidx >= strlen(word)) {
return 1;
}
if (strlen(word) == 1)
return 1;
for (int direction = 0; direction < 8; direction++) {
int nextY = by + dy[direction];
int nextX = bx + dx[direction];
if (map[nextY][nextX] == word[nextidx]) {
;
if (nextFind(nextY, nextX, nextidx , word))
return 1;
}
}
return 0;
}
int startWord(char *word) {
int bx, by;
for (by = 0; by < 5; by++) {
for (bx = 0; bx < 5; bx++) {
if (map[by][bx] = word[0]) {
if (nextFind(by, bx, 0 , word)) {
return 1;
}
}
}
}
return 0;
}
int main(void) {
int testcase , tc;
int i, j;
int num;
printf("input testcase : ");
scanf_s("%d", &testcase);
for (tc = 0; tc < testcase; tc++) {
for (i = 0; i < 5; i++) {
for (j = 0; j < 5; j++) {
printf("input %d by %d : ", i+1, j+1);
cin >> map[i][j];
}
}
printf("input num :");
scanf_s("%d", &num);
for (i = 0; i < num; i++) {
cin >> word;
if (startWord(word))
printf("%s : YES\n", word);
else
printf("%s : NO\n", word);
}
}
}
부가 설명을 하자면 dx와 dy는 좌표상에 이동을 할때
| (-1,1) | (0,1) | (1,1) |
| (-1,0) | (0,0)<- 현재 위치 | (1,0) |
| (-1,-1) | (0,-1) | (1, -1) |
이런식으로 좌표를 그린 것이라고 생각하면된다.
4. 시간 복잡도 분석
마지막 글자에 도달하기 저에 주변의 모든 칸에 대해 재귀 함수를 호출한다. 각 칸에는 최대 여덟개의 구성원이 있고 단어 길이가 N이라면 N-1단계 까지 진행된다. 따라서 시간복잡도는 O(8^(n-1))이다.
5. 후기..
평소에 코딩공부를 많이 안해서 나는 아직 멍청한가보다... 공부하자!
재귀함수를 쓸 때는 항상 기저 조건을 생각하자!