알고스팟 문제 풀이 BOGGLE

레거시/레거시-알고스팟-알고리즘 문제 해결 전략 2019. 10. 8. 16:59

책 "알고리즘 문제 해결 전략"에 나오는 algospot 문제 "BOGGLE"에 대한 풀이입니다.

문제 해결 전략 - 무작정 풀기

먼저 제가 접근한 문제 해결 전략은 "무작정 풀기"입니다.

문제의 입력 분석과 해결 조각 찾기

우리가 문제를 해결하기 위해선는, 5x5의 보드판 board, 길이 10 이하의 문자열 s라는 입력이 필요하다는 것을 알아야 합니다. 실제 테스트 케이스 1개당 문자열 N개를 받습니다만, 결국 이 문제의 핵심은 "보드판에서 인접한 위치만 이동함으로써 문자열을 만들 수 있느냐"입니다. main 함수의 다음 파트를 유의깊게 살펴봐주세요.

//...
for (int i=0; i<N; i++) {
    string s;
    cin >> s;
    bool res = solution(board, s);
    cout << s << " " << ( (res) ? "YES" : "NO" ) << endl;
}
//...

위 코드는 N개만큼 순회하여 문자열 s를 만든 후 board에서 문제를 해결할 수 있는지 여부를 출력하는 부분입니다. 결국 문제를 해결하기 위해선, board와 문자열 s 이 2개면 충분하다는 것이죠.

이번에는 문제를 풀기 위한 조각들을 찾기 위해서 문제의 입력을 분석해보죠. 보드 초기화는 생략하고, 문자열을 입력하여 보드판에서 찾는 것을 봅시다. 먼저 "PRETTY"입니다.

먼저 P를 보드판에서 찾아야 합니다.

그 다음 R을 찾습니다. 다행히 인접한 곳에 R이 존재합니다.

다음은 E입니다.

다음은 T입니다.

다음은 T입니다.

다음은 Y입니다.

문제 페이지에서 찾은 그림은 아니지만, 역시 "PRETTY"라는 문자열이 board 안에 존재하는 것을 확인할 수 있습니다. 이제 "REPEAT"을 찾아볼까요?

첫 문자 R입니다.

현재 R의 위치에서는 인접한 곳에 E가 없습니다.

그럼 보드판 내에 다른 위치의 R을 찾습니다.

이제 인접한 위치에 E가 있습니다. E로 이동하죠.

다음은 P입니다.

다음은 E입니다. 인접한 곳에 무조건 E는 존재합니다. 왜냐하면 우리가 지나온 길이니까요.

다음은 A입니다.

다음은 T입니다.

결국, 이 문제는 보드판의 모든 위치에서 다음을 반복하면 됩니다.

현재 "검사하는 문자의 문자열에서의 위치"를 나타내는 index가 문자열 길이와 같아질 때까지 다음을 반복합니다.
현재 위치 (x, y)가 보드에 존재하는 위치인지 확인합니다.
만약 존재하는 위치라면, 문자열 속 검사하는 문자 s[index]와 보드판의 특정 위치 (x, y)에 저장된 문자 board[x][y]와 비교합니다.
만약 둘이 같은 문자라면, 인접한 곳으로 이동한 후 다음 문자와 비교합니다.

보드의 모든 위치에서 문자열을 표현할 수 있는지 여부를 검사하는 solution 함수

하나씩 쪼개서 생각해봅시다. 먼저 가장 상위의 solution 함수입니다. solution 함수는 보드판의 모든 위치에서 문자열을 표현할 수 있는지 여부를 묻습니다. 순회하는 도중 표현할 수 있는 경우 바로 참을, 순회를 마쳤음에도 표현할 수 없을 때는 거짓을 반환합니다.

bool solution(const vector< vector<char>> & board, const string & s) {
    for (int i=0; i<BOARD_SIZE; i++) {
        for (int j=0; j<BOARD_SIZE; j++) {
            if (solve(board, s, i, j, 0)) {
                return true;
            }
        }
    }

    return false;
}

해당 위치의 타당성을 살피고, 인접한 곳으로 이동하여 다음 문자를 확인하는 재귀 함수 solve 함수

위의 코드에서 solve함수가 바로 보드 상에서 문자열이 표현되는지 여부를 반환하는 함수입니다. solve함수는 재귀 함수로써, 다음의 예외 상황이 존재합니다.

index >= s.length() 일 때 true, 즉 현재 검사하는 문자의 위치를 나타내는 index가 문자열의 길이와 같아질 경우, 문자열 내 모든 문자를 표현했다고 볼 수 있습니다.
(x, y) 가 보드 안에 존재하지 않을 때 false
board[x][y] 와 s[index]가 다를 때 false

여기서 보드 안의 위치 (x, y)에 대해서 보드에 존재하는지 여부를 반환하는 함수가 바로 isRange 입니다. 다음 조건을 만족하는지 확인하는 함수죠.

"0 <= x, y < BOARD_SIZE(=5)"

코드는 다음과 같습니다.

bool isRange(int x, int y) {
    return (0 <= x && x < BOARD_SIZE) && (0 <= y && y < BOARD_SIZE);
}

만약 모든 예외를 통과했다면, 이제 인접한 곳으로 이동해야 합니다. 어떻게 이동할 수 있을까요? 한 좌표당 인접한 곳은 최대 8곳으로 표현할 수 있습니다.

그렇다면 위치 (x, y)일 때, 인접한 곳은 다음과 같이 표현할 수 있겠죠?

이 해당 좌표와 인접한 곳의 좌표들의 차이를 표시한 것이 바로 aroundCoordinates입니다. 코드는 다음과 같습니다.

vector< pair<int, int>> aroundCoordinates = {
    make_pair(-1, 1), // 좌상단
    make_pair(-1, 0), // 좌
    make_pair(-1, -1),// 좌하단
    make_pair(0, -1), // 하
    make_pair(1, -1), // 우하단
    make_pair(1, 0),  // 우
    make_pair(1, 1),  // 우상단
    make_pair(0, 1)   // 상
};

결국, 위 배열을 순회하여, 현재 위치와 인접한 곳의 좌표를 얻고, 다음 문자를 비교하면 됩니다. 이렇게 말이죠.

int solve(const vector< vector<char>> & board, const string & s, int x, int y, int index) {
    // 예외 처리

    for (auto coordinate : aroundCoordinates) {
        int nx = x + coordinate.first;
        int ny = y + coordinate.second;
        int nextIndex = index + 1;

        if (solve(board, s, nx, ny, nextIndex)) {
            return 1;
        }
    }

    return 0;
}

결국 solve의 코드는 다음과 같아집니다.

int solve(const vector< vector<char>> & board, const string & s, int x, int y, int index) {
    if (index >= s.length()) {
        return 1;
    }

    if (!isRange(x, y) || board[x][y] != s[index]) {
        return 0;
    }

    for (auto coordinate : aroundCoordinates) {
        int nx = x + coordinate.first;
        int ny = y + coordinate.second;
        int nextIndex = index + 1;

        if (solve(board, s, nx, ny, nextIndex)) {
            return 1;
        }
    }

    return 0;
}

코드 전문 - 무작정 풀기

다음은 "무작정 풀기 전략"을 통한 알고리즘 풀이 코드 전문입니다. main은 입력에 대해서 예외 처리를 한 후 solution 함수를 부릅니다. 문제 입력을 만드는데 코드를 유의깊게 봐주세요.

#include <iostream>
#include <vector>
#include <string>

using namespace std;

const int BOARD_SIZE = 5;

vector< pair<int, int>> aroundCoordinates = {
    make_pair(-1, 1), // 좌상단
    make_pair(-1, 0), // 좌
    make_pair(-1, -1),// 좌하단
    make_pair(0, -1), // 하
    make_pair(1, -1), // 우하단
    make_pair(1, 0),  // 우
    make_pair(1, 1),  // 우상단
    make_pair(0, 1)   // 상
};


bool isRange(int x, int y) {
    return (0 <= x && x < BOARD_SIZE) && (0 <= y && y < BOARD_SIZE);
}

int solve(const vector< vector<char>> & board, const string & s, int x, int y, int index) {
    if (index >= s.length()) {
        return 1;
    }

    if (!isRange(x, y) || board[x][y] != s[index]) {
        return 0;
    }

    for (auto coordinate : aroundCoordinates) {
        int nx = x + coordinate.first;
        int ny = y + coordinate.second;
        int nextIndex = index + 1;

        if (solve(board, s, nx, ny, nextIndex)) {
            return 1;
        }
    }

    return 0;
}

bool solution(const vector< vector<char>> & board, const string & s) {
    for (int i=0; i<BOARD_SIZE; i++) {
        for (int j=0; j<BOARD_SIZE; j++) {
            if (solve(board, s, i, j, 0)) {
                return true;
            }
        }
    }

    return false;
}

int main() {
    int C;
    cin >> C;

    if ( !(0 < C && C <= 50) ){
        cout << "fail: Test Case Only Between 1 and 50" <<endl;
        return 0;
    }

    for (int i=0; i<C; i++) {
        auto board = vector<vector<char>>(BOARD_SIZE, vector<char>(BOARD_SIZE, '*'));

        for (int i=0; i<BOARD_SIZE; i++) {
            for (int j=0; j<BOARD_SIZE; j++) {
                char c;
                cin >> c;
                board[i][j] = c;

                if ( !(0 <= (c-'A') && (c-'A') <= 26 ) ) {
                    cout << "fail: It only alphabet" << endl;
                    return 0;
                }
            }
        }

        int N;
        cin >> N;

        if ( !(1<=N && N <= 10) ) {
            cout << "fail: N only between 1 and 10" << endl;
            return 0;
        }

        for (int i=0; i<N; i++) {
            string s;
            cin >> s;
            bool res = solution(board, s);
            cout << s << " " << ( (res) ? "YES" : "NO" ) << endl;
        }
    }

    return 0;
}

이 코드를 제출해보면 "시간 초과"라는 결과를 얻을 수 있을 것입니다. 시간 복잡도는 O(8^N)입니다. 결국 무작정 풀기로는 주어진 시간 안에 해결할 수 없다는 것인데, 이 때는 "무작정 풀기" 전략을 바탕으로 최적화하는 방법을 찾아야 합니다. 저는 이 문제를 최적화하기 위해서 "동적 계획법"을 적용하였습니다.

문제 해결 전략 - 동적 계획법

이제 생각해봐야 할 것은 무엇을 최적화하느냐 입니다. 제가 이용할 방법은 동적 계획법입니다. 동적 계획법은 일종의 캐시 전략입니다. 반복되는 호출 값을 저장하여, 이 값을 참조하게 되면 엄청 빠른 속도로 그 값을 가져올 수 있는 것이죠.

재귀 함수의 장점 중 하나는 변하는 속성들에 대해서 반복적인 호출이 바로 보이기 때문에, 동적 계획법을 사용하기 좋은 코드를 바로 만들 수 있다는 것입니다. 여기서 계속 변하는 부분은 함수 원형만 봐도 알 수 있듯 board의 좌표 (x, y)와 검사하는 문자의 위치 index입니다. 즉, x, y, index에 대한 반복 호출에 대한 값을 저장하면 됩니다.

무슨 뜻인지 한 번 살펴보겠습니다. "PRETTY"를 살펴보도록 하죠. "PRETTY"는 다음 3가지의 경로에서 참을 반환합니다.

첫 번째,

두 번째,

세 번째,

이 3가지 경로에서 반복되는 부분은 바로 "TTY" 부분입니다.

즉, x=1, y=4, index=3일 이후 부터는 참으로 가는 경로에 대해 알고 있다는 것입니다. 즉 x=1, y=4, index=3일 때의 상황을 저장하고 있다면, 이것만 참조하면 되겠죠? 결국 동적 해결법으로 문제를 해결하기 위해서 x, y, index 를 가지고 캐싱할 수 있는 3차원 배열을 만들면 됩니다. 여기서 문제의 입력이 중요합니다. 문제를 다시 한 번 잘 읽어봅시다. 입력의 제한 값이 보이나요?

5x5 크기의 알파벳 격자인 게임판
각 단어는 알파벳 대문자 1글자 이상 10글자 이하로 구성됩니다.

결국 index 는 아무리 커봤자 10 이하라는 것입니다. 그렇습니다! 즉, 5 x 5 x 10의 배열을 선언한 후 이 것을 캐시로 이용하면 됩니다. 먼저 문자열 s를 입력하고 board에 존재하는지 확인할 때마다 캐시를 -1로 초기화해주어야 합니다.

main 함수 중 입력 부분,

// ...
for (int i=0; i<N; i++) {
    //추가 부분
    memset(dp, -1, sizeof(dp));
    
    string s;
    cin >> s;
    bool res = solution(board, s);
    cout << s << " " << ( (res) ? "YES" : "NO" ) << endl;
}
//...

그 후, 반복 호출이 존재하는 재귀함수 solve를 이 캐시를 참조하게 만들면 됩니다.

int solve(const vector< vector<char>> & board, const string & s, int x, int y, int index) {
    //예외 처리 부분.

    int & ret = dp[x][y][index];

    if (ret != -1) {
        return ret;
    }

    ret = 0;

    for (auto coordinate : aroundCoordinates) {
        int nx = x + coordinate.first;
        int ny = y + coordinate.second;
        int nextIndex = index + 1;

        if (solve(board, s, nx, ny, nextIndex)) {
            ret = 1;
            return ret;
        }
    }

    return ret;
}

동적 계획법에서 캐시가 초기화 값인 -1이 아닌, 다른 값을 저장하고 있다면, 그 값을 반환해주면 됩니다. 이것이 동적 계획법에 큰 장점입니다. 한 번, 값이 저장이 되었다면 O(1)만에 데이터를 가져와서 비약적인 성능의 향상이 일어나지요. "무작정 풀기"의 solve 함수와 비교해서 보세요. 재귀 호출 디자인의 큰 매력에 빠질 수 있으실겁니다.

코드 전문 - 동적 계획법

다음은 "동적 계획법"을 이용한 알고리즘 풀이 코드 전문입니다. 이전, "무작정 풀기"와 무엇이 차이가 있는지 비교해서 보세요. 참고적으로 다음을 더욱 주의 깊게 살표보세요.

int dp[BOARD_SIZE][BOARD_SIZE][10];
solve - int & ret = dp[x][y][index]; ~ return ret;
main - memset(dp, -1, sizeof(dp));

#include <iostream>
#include <vector>
#include <string>
#include <cstring>

using namespace std;

const int BOARD_SIZE = 5;

vector< pair<int, int>> aroundCoordinates = {
    make_pair(-1, 1), // 좌상단
    make_pair(-1, 0), // 좌
    make_pair(-1, -1),// 좌하단
    make_pair(0, -1), // 하
    make_pair(1, -1), // 우하단
    make_pair(1, 0),  // 우
    make_pair(1, 1),  // 우상단
    make_pair(0, 1)   // 상
};

int dp[BOARD_SIZE][BOARD_SIZE][10];

bool isRange(int x, int y) {
    return (0 <= x && x < BOARD_SIZE) && (0 <= y && y < BOARD_SIZE);
}

int solve(const vector< vector<char>> & board, const string & s, int x, int y, int index) {
    if (index >= s.length()) {
        return 1;
    }

    if (!isRange(x, y) || board[x][y] != s[index]) {
        return 0;
    }

    int & ret = dp[x][y][index];

    if (ret != -1) {
        return ret;
    }

    ret = 0;

    for (auto coordinate : aroundCoordinates) {
        int nx = x + coordinate.first;
        int ny = y + coordinate.second;
        int nextIndex = index + 1;

        if (solve(board, s, nx, ny, nextIndex)) {
            ret = 1;
            return ret;
        }
    }

    return ret;
}

bool solution(const vector< vector<char>> & board, const string & s) {
    for (int i=0; i<BOARD_SIZE; i++) {
        for (int j=0; j<BOARD_SIZE; j++) {
            if (solve(board, s, i, j, 0)) {
                return true;
            }
        }
    }

    return false;
}

int main() {
    int C;
    cin >> C;

    if ( !(0 < C && C <= 50) ){
        cout << "fail: Test Case Only Between 1 and 50" <<endl;
        return 0;
    }

    for (int i=0; i<C; i++) {
        auto board = vector<vector<char>>(BOARD_SIZE, vector<char>(BOARD_SIZE, '*'));

        for (int i=0; i<BOARD_SIZE; i++) {
            for (int j=0; j<BOARD_SIZE; j++) {
                char c;
                cin >> c;
                board[i][j] = c;

                if ( !(0 <= (c-'A') && (c-'A') <= 26 ) ) {
                    cout << "fail: It only alphabet" << endl;
                    return 0;
                }
            }
        }

        int N;
        cin >> N;

        if ( !(1<=N && N <= 10) ) {
            cout << "fail: N only between 1 and 10" << endl;
            return 0;
        }

        for (int i=0; i<N; i++) {
            memset(dp, -1, sizeof(dp));
            string s;
            cin >> s;
            bool res = solution(board, s);
            cout << s << " " << ( (res) ? "YES" : "NO" ) << endl;
        }
    }

    return 0;
}

다음 코드를 제출하면, 0ms 이내로 문제를 통과하는 것을 확인할 수 있습니다.

저작자표시

'레거시 > 레거시-알고스팟-알고리즘 문제 해결 전략' 카테고리의 다른 글

알고스팟 문제 풀이 CLOCKSYNC (0)	2019.10.12
알고스팟 문제 풀이 BOARDCOVER (0)	2019.10.06
알고스팟 문제 풀이 PICNIC (0)	2019.09.27
[알고스팟] 외계 신호 분석(ITES) (0)	2019.01.23
[알고스팟] 조세푸스 문제(JOSEPHUS) (0)	2019.01.23

ABOUT ME

구르미의 개발 이야기 구르미의 개발 이야기

목차

문제 해결 전략 - 무작정 풀기

문제의 입력 분석과 해결 조각 찾기

보드의 모든 위치에서 문자열을 표현할 수 있는지 여부를 검사하는 solution 함수

해당 위치의 타당성을 살피고, 인접한 곳으로 이동하여 다음 문자를 확인하는 재귀 함수 solve 함수

코드 전문 - 무작정 풀기

문제 해결 전략 - 동적 계획법

코드 전문 - 동적 계획법

'레거시 > 레거시-알고스팟-알고리즘 문제 해결 전략' 카테고리의 다른 글

티스토리툴바

ABOUT ME

목차

문제 해결 전략 - 무작정 풀기

문제의 입력 분석과 해결 조각 찾기

보드의 모든 위치에서 문자열을 표현할 수 있는지 여부를 검사하는 solution 함수

해당 위치의 타당성을 살피고, 인접한 곳으로 이동하여 다음 문자를 확인하는 재귀 함수 solve 함수

코드 전문 - 무작정 풀기

문제 해결 전략 - 동적 계획법

코드 전문 - 동적 계획법

'레거시 > 레거시-알고스팟-알고리즘 문제 해결 전략' 카테고리의 다른 글

관련글 관련글 더보기

티스토리툴바