[C언어]Word Search (부루트 포스 탐색 알고리즘)

문제

Word Search

사용자로부터 단어를 입력받아서 해당 단어가 주어진 파일 내에 존재하는지 확인하여, 그 위치를 출력하세요.

• 대소문자는 구분하지 않습니다.
• 알파벳으로만 구성된 파일들의 예시는 input01.txt, input02.txt, input03.txt에서 확인할 수 있습니다.
• 사용자가 입력한 단어를 주어진 문서에서 찾아주되, 첫 줄에서 첫 글자의 위치, 두 번째 줄에는 마지막 글자의 위치를 출력하세요.
• 위치를 출력할 때의 기준은 2차원 배열에서의 index로 상정합니다.
• 예를 들어 아래의 예제에서 CBA를 검색할 경우에는 시작 위치의 index는 0,2, 끝 위치는 0,0이 됩니다.

 

ABCD
BCDA
FDAB
EABG

• 위치 출력 시의 각 차원의 값은 쉼표(,)로 구분해주세요.
• 해당 단어가 여러 개 존재할 경우 2차원 행렬 기준으로 행이 가장 0에 가까운 것부터 열이 가장 0에 가까운 것을 찾아서 하나만 출력하세요.
• 단어 내에 포함된 글자 사이의 연결관계는 상/하/좌/우이며, 대각선 방향으로도 연결될 수 있습니다.
• 단, 연결 방향은 탐색 도중에 바뀌지 않습니다.
• 찾는 단어가 파일 내에 존재하지 않을 경우 -1, -1을 출력하세요.

입출력 예시

아래 예시에서는 make clean all test1로 input01.txt 라는 파일명을 명령행 인자로 전달받아 내용을 읽었다고 가정합니다.

(입력 #1)

parallel

(출력 #1)

0,3
0,10

 

어떻게 해결해야 할까?

간단하게 생각해보면 전체 파일을 순차적으로 탐색하다가 주어진 단어의 처음 알파벳과 일치하면 8개 방향으로 탐색을 진행해보는 쪽으로 해보면 될 것이다.

탐색하는 것은 브루투포스 탐색 알고리즘으로 주어진 문자열의 길이만큼 비교하면서 찾아내는 방식을 사용하면 될 것이다.

 

코드를 살펴보자

전체 코드는 아래와 같다.

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#define ll long long
typedef struct{ int x; int y;}pair;
pair Sidx;
pair Eidx;

int dx[8]= {0,0,-1,1,-1,1,-1,1};
int dy[8] = {-1,1,0,0,-1,1,1,-1};
int search(pair Sidx, int len, char Word[],char wdfile[][256],int linecnt, int filelen){
    for(int d=0; d<8; d++){
        int i;
        for(i=0; i<len; i++){
            int nx = Sidx.x + dx[d]*i;
            int ny = Sidx.y + dy[d]*i;

            if(nx < 0 || ny < 0 || nx >= linecnt || ny >= filelen || tolower(wdfile[nx][ny]) != tolower(Word[i])){
                break;
            }
        }
        if(i==len){
            Eidx.x = Sidx.x + dx[d] * (len-1);
            Eidx.y = Sidx.y + dy[d] * (len-1);
            return 1;
        }
    }
    return 0;
}

int main(int argc, char *argv[]) {
    char Word[1010];
    int numS=0,numE=0;
    //파일 읽어서 배열에 넣기 fffffffuuuuuuu
    char wdfile[1010][256];
    int linecnt = 0;
    FILE *file = fopen(argv[1],"r");
    while(fgets(wdfile[linecnt],256,file)!=NULL && linecnt < 1010){
        wdfile[linecnt][strcspn(wdfile[linecnt],"\n")] = '\0';
        linecnt++;
    }
    fclose(file);

    //탐색을 하기 위한 사전 준비 과정 ccccckkkkkk
    scanf("%s",Word);
    int len = strlen(Word);
    int filelen = strlen(wdfile[0]);
    char S,E;
    S = Word[0];
    E = Word[len-1];
    for(int i=0; i<linecnt; i++){
        for(int j=0; j<filelen; j++)
        {
            if(tolower(wdfile[i][j]) == S)
            {
                Sidx.x = i;
                Sidx.y = j;
                if(search(Sidx,len,Word,wdfile,linecnt, filelen))
                {
                    printf("%d,%d\n",Sidx.x,Sidx.y);
                    printf("%d,%d\n",Eidx.x,Eidx.y);
                    return 0;
                }
            }
        }
    }
    printf("-1,-1");
    return 0;
}

 

일단 전역으로 선언된 부분이다.

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#define ll long long
typedef struct{ int x; int y;}pair;
pair Sidx;
pair Eidx;

int dx[8]= {0,0,-1,1,-1,1,-1,1};
int dy[8] = {-1,1,0,0,-1,1,1,-1};

3가지 헤더 파일을 불러오주었고, 혹시 몰라 long long을 사용할 줄 알고 ll로 정의해놓았지만 사용하진 않았다.

그다음 x좌표와 y좌표를 좀 더 효율적으로 저장하기 위해 pair로 구조체를 선언해주었다.

dx, dy는 8방향 이동을 위한 배열이다.

 

int search(pair Sidx, int len, char Word[],char wdfile[][256],int linecnt, int filelen){
    for(int d=0; d<8; d++){
        int i;
        for(i=0; i<len; i++){
            int nx = Sidx.x + dx[d]*i;
            int ny = Sidx.y + dy[d]*i;

            if(nx < 0 || ny < 0 || nx >= linecnt || ny >= filelen || tolower(wdfile[nx][ny]) != tolower(Word[i])){
                break;
            }
        }
        if(i==len){
            Eidx.x = Sidx.x + dx[d] * (len-1);
            Eidx.y = Sidx.y + dy[d] * (len-1);
            return 1;
        }
    }
    return 0;
}

이 부분은 8가지 방향으로 탐색하는 함수이다. 범위가 넘어가지 않는 선에서 모든 8가지 방향으로 뻗어나가고 만약 문자열을 발견하면 마지막 알파벳이 있는 인덱스를 저장한다. 그 뒤 1을 반환, 끝까지 찾지 못하면 0을 반환한다.

int main(int argc, char *argv[]) {
    char Word[1010];
    int numS=0,numE=0;
    //파일 읽어서 배열에 넣기 fffffffuuuuuuu
    char wdfile[1010][256];
    int linecnt = 0;
    FILE *file = fopen(argv[1],"r");
    while(fgets(wdfile[linecnt],256,file)!=NULL && linecnt < 1010){
        wdfile[linecnt][strcspn(wdfile[linecnt],"\n")] = '\0';
        linecnt++;
    }
    fclose(file);

이 부분은 파일을 읽어와서 한줄씩 2차원 배열에 저장하는 부분이다.

테스트 파일을 넣고 돌리면 argv명령버퍼의 1번 인덱스에 파일 이름이 저장되서 argv[1]을 파일 이름 부분에 넣어주면 된다.

 //탐색을 하기 위한 사전 준비 과정 ccccckkkkkk
    scanf("%s",Word);
    int len = strlen(Word);
    int filelen = strlen(wdfile[0]);
    char S,E;
    S = Word[0];
    E = Word[len-1];
    for(int i=0; i<linecnt; i++){
        for(int j=0; j<filelen; j++)
        {
            if(tolower(wdfile[i][j]) == S)
            {
                Sidx.x = i;
                Sidx.y = j;
                if(search(Sidx,len,Word,wdfile,linecnt, filelen))
                {
                    printf("%d,%d\n",Sidx.x,Sidx.y);
                    printf("%d,%d\n",Eidx.x,Eidx.y);
                    return 0;
                }
            }
        }
    }
    printf("-1,-1");
    return 0;
}

이 부분은 단어를 탐색하기 위한 전처리 과정과 함수가 1을 반환하면 그 인덱스를 출력하며 멈추고 모든 구간을 돌았을 때까지 찾지 못하면 (-1,-1)을 출력하는 부분이다.