백준 3085 사탕 게임

문제 링크: https://www.acmicpc.net/problem/3085

3085번: 사탕 게임

모든 인접한 두칸에 대하여,

1. 서로 사탕을 교환하고나서

2. 먹을수 있는 최대 사탕 갯수를 구하고

3. 그 갯수가 지금까지 구한 최대 사탕 갯수보다 크면, 최대값을 update 시키고

4. 다시 사탕을 원위치 시킨다.

 

먼저 아래의 코드는 AC를 못받은 코드이다. 아래에서 max_cnt를 update 해주는 위치가 틀렸다.

예를 들어 어떤 두개의 사탕을 교환한 후에 한 row에서 BAAAABAA 이런식으로 사탕이 있다고 하면, 4개의 사탕을 먹을수 있는데 아래 코드는 2개의 사탕을 먹을수 있다고 계산한다.

#include <bits/stdc++.h>
using namespace std;
 
char a[51][51];
int n, dy[4] = {-1, 1, 0, 0}, dx[4] = {0, 0, -1, 1};
 
int maxCandy() {
    int max_cnt = 0;
    for(int i = 0; i < n; i++) {
        int cnt = 1;
        for(int j = 1; j < n; j++) {
            if(a[i][j] == a[i][j - 1]) cnt++;
            else cnt = 1;
        }
        max_cnt = max(max_cnt, cnt);
    }
 
    for(int j = 0; j < n; j++) {
        int cnt = 1;
        for(int i = 1; i < n; i++) {
            if(a[i][j] == a[i - 1][j]) cnt++;
            else cnt = 1;
        }
        max_cnt = max(max_cnt, cnt);
    }
 
    return max_cnt;
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> n;
    for(int i = 0; i < n; i++) for(int j = 0; j < n; j++)
        cin >> a[i][j];
 
    int ans = 0;
    for(int y = 0; y < n; y++) for(int x = 0; x < n; x++) {
        for(int d = 0; d < 4; d++) {
            int yy = y + dy[d], xx = x + dx[d];
            if(yy >= 0 && xx >= 0 && yy < n && xx < n) {
                swap(a[y][x], a[yy][xx]);
                ans = max(ans, maxCandy());
                swap(a[y][x], a[yy][xx]);
            }
        }
    }
 
    cout << ans << '\n';
    return 0;
}
 

아래 코드는 max_cnt를 update 해주는 위치를 바꿔서 AC를 받은 코드이다.

#include <bits/stdc++.h>
using namespace std;
 
char a[51][51];
int n, dy[4] = {-1, 1, 0, 0}, dx[4] = {0, 0, -1, 1};
 
int maxCandy() {
    int max_cnt = 0;
    for(int i = 0; i < n; i++) {
        int cnt = 1;
        for(int j = 1; j < n; j++) {
            if(a[i][j] == a[i][j - 1]) cnt++;
            else cnt = 1;
            max_cnt = max(max_cnt, cnt);
        }
    }
 
    for(int j = 0; j < n; j++) {
        int cnt = 1;
        for(int i = 1; i < n; i++) {
            if(a[i][j] == a[i - 1][j]) cnt++;
            else cnt = 1;
            max_cnt = max(max_cnt, cnt);
        }
    }
 
    return max_cnt;
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> n;
    for(int i = 0; i < n; i++) for(int j = 0; j < n; j++)
        cin >> a[i][j];
 
    int ans = 0;
    for(int y = 0; y < n; y++) for(int x = 0; x < n; x++) {
        for(int d = 0; d < 4; d++) {
            int yy = y + dy[d], xx = x + dx[d];
            if(yy >= 0 && xx >= 0 && yy < n && xx < n) {
                swap(a[y][x], a[yy][xx]);
                ans = max(ans, maxCandy());
                swap(a[y][x], a[yy][xx]);
            }
        }
    }
 
    cout << ans << '\n';
    return 0;
}
 

위의 두코드는 물론 시간내에 충분히 돌아가기는 하지만, 모든 칸에 대해서 상하좌우에 있는 4개의 칸과 교환을 하다보니, 중복해서 교환하는 경우가 많다. 그래서 중복해서 교환하는 경우를 없애기 위해서 모든 칸을 기준으로 오른쪽과 아래에 있는 칸들과만 교환하는것으로 구현해봤다. (물론 마지막 column에 있는 칸들은 아래에 있는 칸과, 마지막 row에 있는 칸들은 오른쪽에 있는 칸과 교환)

#include <bits/stdc++.h>
using namespace std;
 
int n;
char a[51][51];
 
int candy() {
    int max_cnt = 0;
    for(int i = 0; i < n; i++) {
        int cnt = 1;
        for(int j = 1; j < n; j++) {
            if(a[i][j] == a[i][j - 1]) cnt++;
            else cnt = 1;
            max_cnt = max(max_cnt, cnt);
        }
    }
 
    for(int j = 0; j < n; j++) {
        int cnt = 1;
        for(int i = 1; i < n; i++) {
            if(a[i][j] == a[i - 1][j]) cnt++;
            else cnt = 1;
            max_cnt = max(max_cnt, cnt);
        }
    }
 
    return max_cnt;
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> n;
    for(int i = 0; i < n; i++) for(int j = 0; j < n; j++)
        cin >> a[i][j];
 
    int ans = 0;
    for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) {
        if(i < n - 1) {
            swap(a[i][j], a[i + 1][j]);
            ans = max(ans, candy());
            swap(a[i][j], a[i + 1][j]);
        }
        if(j < n - 1) {
            swap(a[i][j], a[i][j + 1]);
            ans = max(ans, candy());
            swap(a[i][j], a[i][j + 1]);
        }
    }
 
    cout << ans << '\n';
    return 0;
}
 

중복해서 교환하는 경우를 지웠더니, 시간도 약 반정도로 줄었다.