[BOJ] 백준 3085 사탕 게임 / 완전 탐색(Brute-force Search)

* 예외 처리를 잘하자

 

이미지를 클릭하면 문제 사이트로 이동합니다.

---

💣 문제 이해

 

1. 행으로 인접한 두 칸을 고르고 교환한다(swap)

2. 행과 열에서 가장 길게 연속해있는 사탕개수를 찾는다.

3. 열로 인접한 두 칸을 고르고 교환한다(swap)

4. 행과 열에서 가장 길게 연속해있는 사탕개수를 찾는다.

 

보통 컴퓨터가 1초에 약 1억번의 연산을 한다.

이 문제에서 배열의 최대 크기라고 해봐야 50*50 이므로 단순하게 모든 경우를 하나하나 따져보아도

50*50*(50*50+50*50) = 12,500,000 이므로

완전 탐색(Brute-force Search) 방식을 사용하기로 했다.

 

💭 풀이 과정

 

작성 언어: C++

 

#include <cstdio>
#include <algorithm>
using namespace std;

int num = 0;
char arr[60][60] = {0,};

int check(){
    int count = 1, ret = 0;
    // 행으로 최대치 카운트
    for (int i = 1; i <= num; ++i) {
        for (int j = 1; j <= num-1; ++j) {
            if(arr[i][j] == arr[i][j+1]){
                ++count;
            }else{
                ret = max(count, ret);
                count = 1;
            }
        }
        // num = 6이고 YYYYYY여서 else를 안거치는 경우를 처리. count도 초기화.
        ret = max(count, ret);
        count = 1;
    }
    // 열로 최대치 카운트
    for (int i = 1; i <= num; ++i) {
        for (int j = 1; j <= num-1; ++j) {
            if(arr[j][i] == arr[j+1][i]){
                ++count;
            }else{
                ret = max(count, ret);
                count = 1;
            }
        }
        // num = 6이고 YYYYYY여서 else를 안거치는 경우를 처리. count도 초기화.
        ret = max(count, ret);
        count = 1;
    }
    return ret;
}

int main(){
    int answer = 0;
    scanf(" %d", &num);
    for (int i = 1; i <= num; ++i) {
        for(int j = 1; j <= num; ++j) {
            scanf(" %c", &arr[i][j]);
        }
    }
    
    for (int i = 1; i <= num; ++i) {
        for (int j = 1; j <= num-1; ++j) {
            // 행 내에서 교환
            swap(arr[i][j], arr[i][j+1]);
            answer = max(check(), answer);
            swap(arr[i][j], arr[i][j+1]);
            // 열 내에서 교환
            swap(arr[j][i], arr[j+1][i]);
            answer = max(check(), answer);
            swap(arr[j][i], arr[j+1][i]);
        }
    }
    printf("%d\n", answer);
    return 0;
}

 

🏆 배운 점

 

분명 접근 방식은 맞는 것 같고 코드도 딱히 틀린 부분을 찾지 못해서 오답처리가 몇 번이나 반복되었다.

답답해서 구글링 하던 중에 찾은 부분이 바로 소스에도 주석처리 해둔 케이스이다.

 

행에 YYYYYY 같이 같은 사탕으로만 나열되어 있는 경우, else를 지나지 못해서 ret이 갱신되지 못한다...

그래서 num이 6이고 배열을 Y로 채우자 61이라는 답이 나왔다.

count가 초기화 되지 않아 계속해서 증가하는 최악의 사태가 발생하는 것이다.

 

행 또는 열이 같은 사탕으로 채워져 있는 경우를 처리하자 정답 통과가 되었다!!!

 

당연한 생각일 수도 있지만,

오답 이유를 모르겠다면 직접 케이스를 만들어 따져보자!!