3085_사탕게임

❌틀린 코드❌

브루트포스 문제였다.

가로로 교환하는 경우, 세로로 교환하는 경우에 대해 최대 길이를 구하면 된다.

'가장 긴 연속 부분'이 상,하,좌,우 로 연결된 것이 아닌, 막대 모양을 말한다는 점에 주의해야 한다.
처음에 문제를 잘못 읽어서 dfs로 상,하,좌,우 를 탐색하는 실수를 했다. (아래 코드)

#include <iostream>
#include <algorithm>
#include <cstring>
#define MAX 50

using namespace std;

int n, ans = 0;
int dx[] = { 0,0,-1,1 };
int dy[] = { -1,1,0,0 };
char arr[MAX][MAX];
bool visited[MAX][MAX];

void dfs(int sx, int sy, int cnt) {
    if (visited[sx][sy]) return;
    visited[sx][sy] = true;
    if (ans < cnt) ans = cnt;
    for (int i = 0; i < 4; i++) {
        int nx = sx + dx[i];
        int ny = sy + dy[i];
        if (0 <= nx && nx < n && 0 <= ny && ny < n) {
            if (arr[nx][ny] == arr[sx][sy]) {
                dfs(nx, ny, cnt + 1);
            }
        }
    }
}

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

    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> arr[i][j];
        }
    }
    // 가로
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n - 1; j++) {
            // 양옆 바꾸기
            swap(arr[i][j], arr[i][j + 1]);
            // 최대 길이 탐색
            for (int k = 0; k < n; k++) {
                for (int l = 0; l < n; l++) {
                    memset(visited, 0, sizeof(visited));
                    dfs(k, l, 0);
                }
            }
            swap(arr[i][j], arr[i][j + 1]);
        }
    }
    // 세로
    for (int j = 0; j < n; j++) {
        for (int i = 0; i < n - 1; i++) {
            // 위아래 바꾸기
            swap(arr[i][j], arr[i + 1][j]);
            // 최대 길이 탐색
            for (int k = 0; k < n; k++) {
                for (int l = 0; l < n; l++) {
                    memset(visited, 0, sizeof(visited));
                    dfs(k, l, 0);
                }
            }
            swap(arr[i][j], arr[i + 1][j]);
        }
    }
    cout << ans << '\n';
    return 0;
}

 

⭕맞는 코드⭕

막대 모양만 탐색하게끔 코드를 수정했다. 단순히 for문으로 탐색하면 되는 간단한 문제였다.

#include <iostream>
#include <algorithm>
#define MAX 50

using namespace std;

int n, ans = 0;
char arr[MAX][MAX];

void get_max() { // 최대 길이 탐색
    for (int i = 0; i < n; i++) { // 가로
        int cnt = 1;
        for (int j = 0; j < n - 1; j++) {
            if (arr[i][j] == arr[i][j + 1]) {
                cnt++;
                if (cnt > ans) ans = cnt;
            }
            else {
                cnt = 1;
            }
        }
    }
    for (int j = 0; j < n; j++) { // 세로
        int cnt = 1;
        for (int i = 0; i < n - 1; i++) {
            if (arr[i][j] == arr[i + 1][j]) {
                cnt++;
                if (cnt > ans) ans = cnt;
            }
            else {
                cnt = 1;
            }
        }
    }
}

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

    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> arr[i][j];
        }
    }
    // 양옆 바꾸기
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n - 1; j++) {
            swap(arr[i][j], arr[i][j + 1]);
            get_max();
            swap(arr[i][j], arr[i][j + 1]);
        }
    }
    // 위아래 바꾸기
    for (int j = 0; j < n; j++) {
        for (int i = 0; i < n - 1; i++) {
            swap(arr[i][j], arr[i + 1][j]);
            get_max();
            swap(arr[i][j], arr[i + 1][j]);
        }
    }
    cout << ans << '\n';

    return 0;
}