[알고리즘 문제 해결 전략] Part 1. 6장 무식하게 풀기

알고리즘 문제해결 전략 1 권, 흔히 불리는 이름은 종만북 ! 

그럼 이제,,, 시작.. ( 내 글이랑 문제 글 색이랑 같아서 색을 수정 했다... ) 

6장 무식하게 풀기, 완전 탐색? 으로 모든 경우의 수를 찾아서 답을 찾아내는 방식

1. 예제 : 보글 게임 (문제 : ID : BOGGLE, 난이도 : 하)

https://algospot.com/judge/problem/read/BOGGLE 

보글(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

6장 내용이 무식하게 풀기라서 완탐으로 찾기 했었다. 

시간초과가 발생했고, 보통 BFS / DFS 는 visited 배열을 만들어서 

방문 했던 위치는 통과하는데 그 부분을 빠뜨렸다..  (위에 보면 빨간색으로 바꿔놓은 글이 그 부분이다.)

다른 정답 코드를 참고하여 다시 완성 !!

배열 쓰기 귀찮아서 string 했는데 4ms 속도가 나온다... C로 작성하면 0ms 가 될 것임!

#include <iostream>
#include <string>
using namespace std;
int C,N,ans;
int dis[8][2]={{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}}; // 8 방향
int memo[5][5][10];
string pan[6];
string sent[10];
 
 
void dfs(int y, int x, int tidx, int sidx, int total, int now);
 
int main(){
    cin >> C;
    for(int tc = 0; tc < C; tc++){
        //판 초기화
        for(int i=0; i<6; i++)
            pan[i].clear();
        //문장 초기화
        for(int i=0; i<10; i++)
            sent[i].clear();
        //판 입력
        for(int i=0; i<5; i++)
            cin >> pan[i];
        //문장 갯수
        cin >> N;
        //문장 입력
        for(int i=0; i<N; i++)
            cin >> sent[i];
        //문장 검출
        for(int i=0; i<N; i++){
            ans = 0;    //플래그 설정
            //메모이제이션 용 배열 초기화
            for(int j=0; j<5; j++)
                for(int k=0; k<5; k++)
                    for(int l=0; l<10; l++)
                        memo[j][k][l] = 0;
            //판 전체에서 첫글자 확인하고 시작
            for(int j=0; j<5; j++){
                for(int k=0; k<5; k++){
                    if(pan[j][k] == sent[i][0]){
                        dfs(j, k, i, 0, (int)sent[i].size(), 1);
                        if(ans == 1)    //문장 찾았으면 중단
                            break;
                    }
                }
                if(ans == 1)    //문장 찾았으면 중단
                    break;
            }
            //플래그로 답 출력
            if(ans == 0){
                cout << sent[i] << " " << "NO" << endl;
            }else if(ans == 1){
                cout << sent[i] << " " << "YES" << endl;
            }
        }
    }
}
 
void dfs(int y, int x, int tidx, int sidx, int total, int now){
    memo[y][x][sidx] = 1;   //판에서 글자를 찾았을때 몇번째 문자인지 기억
    if(total == now){       //찾는 문자의 갯수와 지금 현재 문자 위치의 수 비교
        ans = 1;
        return;
    }
    
    int ty = y;
    int tx = x;
 
    for(int i=0; i<8; i++){ //8 방향 모두 검색
        ty = y + dis[i][0];
        tx = x + dis[i][1];
        if(ty < 0 || tx < 0 || ty > 4 || tx > 4) continue; // 범위 초과시 종료
        if(pan[ty][tx] == sent[tidx][sidx+1]){  //다음 문자를 확인
            if(memo[ty][tx][sidx+1] == 1) continue; //해당 자리에 같은 문장의 같은 문자 위치면 pass
            dfs(ty, tx, tidx, sidx + 1, total, now + 1);    // 재귀함수
        }
    }
    return;
}
 

질의 응답에서 테스트 케이스를 발견 했고 아래와 같음.

출처  ID : digression99 

계속 오답나는 분들은 이 테스트 케이스를 시도해보세요.

// testcase
//4
//URLPM
//XPRET
//GIAET
//XTNZY
//XOQRS
//10
//PRETTY
//GIRL
//REPEAT
//KARA
//PANDORA
//GIAZAPX
//REPEAT
//KARA
//PANDORA
//URLPMPMPMM
//NNNNS
//NEEEN
//NEYEN
//NEEEN
//NNNNN
//4
//YESR
//SNNNNNNN
//EEEEEEEEE
//NEYN
//NNNNN
//NEEEN
//NEYEN
//NEEEN
//NSNNN
//1
//YES
//AAAAA
//AAAAA
//AAAAA
//AAAAA
//AAAAB
//4
//ABABABABAA
//AAAAAAAAAB
//ABABABABBA
//BAAAAAAABA

// result
//PRETTY YES
//GIRL YES
//REPEAT YES
//KARA NO
//PANDORA NO
//GIAZAPX YES
//REPEAT YES
//KARA NO
//PANDORA NO
//URLPMPMPMM NO
//YESR NO
//SNNNNNNN YES
//EEEEEEEEE YES
//NEYN NO
//YES YES
//ABABABABAA YES
//AAAAAAAAAB YES
//ABABABABBA NO
//BAAAAAAABA YES

끝 ! 앞으로 책의 커리큘럼은 아니지만, 문제 풀이용으로 풀어 나갈 것!