algospot - BOGGLE
문제
보글(Boggle) 게임은 그림 (a)와 같은 5x5 크기의 알파벳 격자인 게임판의 한 글자에서 시작해서 펜을 움직이면서 만나는 글자를 그 순서대로 나열하여 만들어지는 영어 단어를 찾아내는 게임입니다. 펜은 상하좌우, 혹은 대각선으로 인접한 칸으로 이동할 수 있으며 글자를 건너뛸 수는 없습니다. 지나간 글자를 다시 지나가는 것은 가능하지만, 펜을 이동하지않고 같은 글자를 여러번 쓸 수는 없습니다.
예를 들어 그림의 (b), (c), (d)는 각각 (a)의 격자에서 PRETTY, GIRL, REPEAT을 찾아낸 결과를 보여줍니다.
보글 게임판과 알고 있는 단어들의 목록이 주어질 때, 보글 게임판에서 각 단어를 찾을 수 있는지 여부를 출력하는 프로그램을 작성하세요.
입력
입력의 첫 줄에는 테스트 케이스의 수 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
코드
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
char boggle[7][7];
char buf[100];
char word[10][11];
int prev[2][10];
int start[7][7];
int mark[7][7][10];
int loc[2];
int idx;
int len;
int move[8][2] = {{-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}};
int main(){
char temp;
int row_ct, col_ct;
int C, N;
int i, j, k, t, p, q, offset, x, y, result;
scanf("%d%c", &C, &temp);
for(i = 0; i < C; i++){
for(j = 0; j < 7; j++){
for(k = 0; k < 7; k++){
boggle[j][k] = 0;
}
}
for(j = 1; j < 6; j++){
scanf("%s", &boggle[j][1]);
}
scanf("%d%c", &N, &temp);
for(j = 0; j < N; j++){
scanf("%s", word[j]);
}
for(j = 0; j < N; j++){
result = 0;
len = strlen(word[j]);
for(x = 1; x < 6; x++){
for(y = 1 ; y < 6; y++){
if(boggle[x][y] == word[j][0]){
memset(mark, 0, sizeof(mark));
idx = 0;
loc[0] = x;
loc[1] = y;
prev[0][idx] = x;
prev[1][idx] = y;
idx++;
while(idx < len){
for(k = 0; k < 8; k++){
if(mark[loc[0] + move[k][0]][loc[1] + move[k][1]][idx] == 0 && boggle[loc[0] + move[k][0]][loc[1] + move[k][1]] == word[j][idx]){
loc[0] = loc[0] + move[k][0];
loc[1] = loc[1] + move[k][1];
prev[0][idx] = loc[0];
prev[1][idx] = loc[1];
idx++;
break;
}
}
if(k == 8){
idx--;
mark[loc[0]][loc[1]][idx] = 1;
if(idx == 0)
break;
loc[0] = prev[0][idx-1];
loc[1] = prev[1][idx-1];
}
}
if(idx == len){
result = 1;
break;
}
}
}
if(result == 1)
break;
}
if(result == 1){
printf("%s YES\n", word[j]);
}
else{
printf("%s NO\n", word[j]);
}
}
}
}해설
다이나믹 프로그래밍에 관한 문제이다. 재귀 함수로 짤 수도 있지만 귀찮아서 반복문으로 해결 했다. 문제 해결 스텝은 다음과 같다.
do 글자 탐색
>>if 글자가 있을 경우,
위치 정보를 저장하고 인덱스 증가
else 글자가 없을 경우,
막다른 길로 표시하고 인덱스 감소 후 다시 위치 지정
중요한 점은 글자 탐색 조건에 표시(mark 배열)한 곳에 대한 조건도 같이 넣어줘야 한다는 점이다.
낙서
문제를 잘못 읽어서 삽질을 너무 많이 한 문제이다. '보글(Boggle) 게임은 그림 (a)와 같은 5x5 크기의 알파벳 격자인 게임판의 한 글자에서 시작해서 펜을 움직이면서 만나는 글자를 그 순서대로 나열하여 만들어지는 영어 단어를 찾아내는 게임입니다.' 이 문장에서 순서대로란 말에 주목했어야 하는데, 순서대로란 말은 즉 현재 위치에서 펜을 한칸만 움직여서 다음 글자에 도달할 수 있어야 한다는 것이다. 처음에는 이 말을 빼먹고 문제를 읽어서 그냥 현재까지 찾은 글자들에 인접한 곳에 다음 글자가 있으면 되는 문제로 생각해서 굉장히 복잡하게 풀고 있다가, 문제를 다시 읽고 허무해졌다. 문제를 잘 읽자!