[백준 / C++] 3085번 사탕 게임

문제 재정의 및 추상화

결론: 행 또는 열을 기준으로 사탕을 하나씩 교환해보며 가장 긴 행이나 열의 사탕 개수를 구하라 쉽게 말하자면 애니팡

문제 접근 방식

• 행, 열 개념을 가진 N x N의 사탕 보드가 주어진다.
  -> 2차원 배열을 이용한다.
• 인접한 두 칸의 사탕을 교환하고 길이를 확인하여 최대 연속값을 찾는다.
  -> swap 함수를 통해 모든 칸을 다 교환해보며 최댓값을 찾는다.

해법을 찾는데 결정적이었던 깨달음

📌 별다른 방법이 없다! 완전 탐색으로 간다!

문제 풀이 로직

0. 최대 길이를 구하는 함수를 먼저 작성한다.
   0-1. 행 열 순으로 이중 for문을 돌며 한 행마다 연속된 사탕이 나오는 경우를 센다.
   0-2. 이 때 연속된 사탕이 나오지 않는다면 최대 개수와 비교하여 최대 개수 혹은 1로 경우의 수를 초기화해준다.
   0-3. 열 행 순으로 이중 for문을 돌며 한 열마다 연속된 사탕이 나오는 경우를 위와 같이 센다.
1. 보드의 크기 n을 입력 받는다.
2. 이중 for문을 돌며 보드에 들어갈 사탕 색상을 입력받는다.
3. 행 열 순으로 이중 for문을 돌며 열 기준으로 사탕을 바꿀 때마다 함수를 이용해 최대 길이를 구해보고 다시 원래대로 돌려준다.
4. 열 행 순으로 이중 for문을 돌며 행 기준으로 사탕을 바꿀 때마다 함수를 이용해 최대 길이를 구해보고 다시 원래대로 돌려준다.
5. 최대 길이를 구하는 함수에서 구한 최대 개수를 출력한다.

문제 풀이

#include <bits/stdc++.h>
using namespace std;

int n;
int maxNum = 0;
char board[51][51];

void check(){
// 최장 행 길이 구하기
    for(int i = 0; i < n; i++){ 
        int cnt = 1;
        for(int j = 0; j < n; j++){
            if(board[i][j] == board[i][j + 1]) cnt++;
            else{
                if(maxNum < cnt) maxNum = cnt;
                cnt = 1;
            }
        }
    }
    
// 최장 열 길이 구하기
    for(int j = 0; j < n; j++){ 
        int cnt = 1;
        for(int i = 0; i < n; i++){
            if(board[i][j] == board[i + 1][j]) cnt++;
            else{
                if(maxNum < cnt) maxNum = cnt;
                cnt = 1;
            }
        }
    }
}

int main(){
    cin >> n;
    
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin >> board[i][j];
        }
    }

// 열 바꾸기 == 최장 열 탐색
    for(int i = 0; i < n; i++){ 
        for(int j = 0; j < n - 1; j++){
            swap(board[i][j], board[i][j + 1]);
            check();
            swap(board[i][j], board[i][j + 1]);
        }
    }
    
// 행 바꾸기 == 최장 행 탐색
    for(int j = 0; j < n; j++){ 
        for(int i = 0; i < n - 1; i++){
            swap(board[i][j], board[i + 1][j]);
            check();
            swap(board[i][j], board[i + 1][j]);
        }
    }
    
    cout << maxNum;
    
    return 0;
}