[Algorithm] 백준 - 사탕 게임 (3085번)

문제

[백준] 사탕 게임
(Olympiad > Croatian Highschool Competitions in Informatics > 2012 > Junior Croatian Olympiad in Informatics - Exam #1 )

사용 알고리즘

 

- 브루트포스 (Brute Force)

해결방법

• 이 문제의 핵심은, 바꾼 사탕이 위치한 행, 열 만 탐색하는게 아닌, 전체 보드판을 다 탐색해야 한다는 것 !
  
  • 예제 2번을 살펴보면, C(1,0), Y(1,1) 두 사탕을 swap 한 후 (0,0) 부터 행방향 탐색을 했을 때, [P, P, P, P] 로 연속한 N개의 사탕이 확인되므로 탐색이 종료된다.

예제 2

• 보드판의 (0,0)부터 마지막 사탕까지 쭉 반복문을 돌면서, 인접한 사탕 (가로 방향, 세로 방향) 을 swap 시키고, 전체 보드판을 탐색(return_max_candy())하면서 연속한 사탕이 있는지 체크한다.
  • return_max_candy(true) : 가로방향(행) 체크
  • return_max_candy(false) : 세로방향(열) 체크
• 연속한 사탕의 개수가 N인 경우 탐색을 종료한다.

소스코드

사용언어 : C++

#include <iostream>
#include <algorithm>

using namespace std;

int N;
char candy_board[51][51];

int return_max_candy(int dir) // 방향(행/열)
{
    int max_num, res = 0;
    char now_candy;

    for (int i=0; i<N; i++){
        now_candy = dir ? candy_board[i][0] : candy_board[0][i];
        max_num = 1;
        for (int j=1; j<N; j++){
            if (now_candy == (dir ? candy_board[i][j] : candy_board[j][i])) {
                max_num++;
            } else {
                max_num = 1;
            }
            now_candy = dir ? candy_board[i][j] : candy_board[j][i];
            res = max(res, max_num);
        }
    }

    return res;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> N;

    // 캔디보드 채우기
    for (int i=0; i<N; i++){
        for (int j=0; j<N; j++){
            cin >> candy_board[i][j];
        }
    }

    int res = -1;

    // 탐색
    for (int i=0; i<N; i++){
        for (int j=0; j<N-1; j++){
            // 가로 swap
            if (candy_board[i][j] != candy_board[i][j+1]) {
                swap(candy_board[i][j], candy_board[i][j+1]);
                res = max(res, max(return_max_candy(1), return_max_candy(0)));
                if (res == N) break;

                // 원복
                swap(candy_board[i][j], candy_board[i][j+1]);
            }

            // 세로 swap
            if (candy_board[j][i] != candy_board[j+1][i]) {
                swap(candy_board[j][i], candy_board[j+1][i]);
                res = max(res, max(return_max_candy(1), return_max_candy(0)));
                if (res == N) break;

                // 원복
                swap(candy_board[j][i], candy_board[j+1][i]);
            }
        }
    }

    cout << res;
}

브루트포스 알고리즘

* 완전탐색 알고리즘 : 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져온다

* 해가 하나 이상 존재한다는 가정을 세우고 모든 범위를 탐색하기 때문에 무조건 정답을 찾을 수 있다

* 장점 : 설계 및 구현이 쉽다

* 단점 : 실행 시간이 오래 걸린다. 메모리 효율이 비효율적이다

https://foreverhappiness.tistory.com/104

https://hcr3066.tistory.com/26

 

 

한줄평

브루트포스가 뭔가 했는데 그냥 전체 탐색하는 거였다 ㅎㅎ