백준 3085. 사탕 게임

https://www.acmicpc.net/problem/3085

3085번: 사탕 게임

 

- 금방 풀어놓고 i,j 위치 하나 잘못써서 애를 먹었다..

 

문제가 처음에 잘 이해가 안갔고 솔직히 아직까지도 뭔가 이상하다고 생각이든다.

"상근이는 사탕의 색이 다른 인접한 두칸을 고르고, 고른 칸에 들어있는 사탕을 서로 교환한다"

고 문제가 되어있는데 이상하다고 생각이 든것은

 

문제를 그대로 해석하자면 상근이는 사탕의 색이 다른 인접한 두칸을 고르고 무조건 한번은 서로 자리를 바꿔야한다.

 

그런데 예제2번을 보면 다음과 같이 입력이 나와있는데

 

4

PPPP

CYZY

CCPY

PPCC

 

이 입력에 대한 답이 4로 나와있다.

 

문제 대로라면 사탕의 색이 서로다른 인접한 두칸을 골라 자리를 바꿔야 하는데 그 경우 아무리 생각해봐도 4가 나올수 없다.

답이 4가 나오려면 자리를 아예 안바꾸거나, 서로 같은 인접한 두칸을 골라 자리를 바꿀수 있어야 한다.

...

 

아무리 생각해도 문제 조건대로 풀면 답이 안나와서 서로 같은 인접한 두칸을 골라 자리를 바꿔도 된다는 조건으로 풀었다.

 

브루트포스 방식으로 모든 칸을 상하 또는 좌우로 색을 바꿔본 후에

보드에서 가장 긴 길이가 몇인지 찾으면 된다.

 

#include <iostream>
using namespace std;

int n;
char board[51][51];

int ans = 0;

// 현재 board에서 가장 긴 문자열의 수를 구해서 ans에 갱신함
void Calculate() {
    int hor_longest = 0;
    int ver_longest = 0;

    for(int i = 0; i < n; i++) {
        char hor_col = board[i][0];
        char ver_col = board[0][i];

        int hor_len = 1;
        int ver_len = 1;

        for(int j = 1; j < n; j++) {
            if(board[i][j] == hor_col) {
                hor_len++;
            }
            else {
                hor_longest = max(hor_len, hor_longest);
                hor_col = board[i][j];
                hor_len = 1;
            }

            if(board[j][i] == ver_col) {
                ver_len++;
            }
            else {
                ver_longest = max(ver_len, ver_longest);
                ver_col = board[j][i];
                ver_len = 1;
            }

        }
        hor_longest = max(hor_len, hor_longest);
        ver_longest = max(ver_len, ver_longest);
    }
    int bigger = max(ver_longest, hor_longest);

    ans = max(ans, bigger);

}


// r을 to_r로, c를 to_c로 바꿔서 가장긴 문자열을 계산하고 원상태로 되돌림
void Swap(int r, int c, int to_r, int to_c) {
    // 원래 board[r][c]에 있던 값 보존
    char original = board[r][c];

    // 자리 바꿈
    board[r][c] = board[to_r][to_c];
    board[to_r][to_c] = original;

    // 가장긴 문자열 계산
    Calculate();

    // 원래자리로 돌림
    board[to_r][to_c] = board[r][c];
    board[r][c] = original;
}

int main() {
    cin >> n;

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

    // 보드의 하나의 좌표를 기준으로 위아래로 swap함
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {

            // 위아래 swap
            if(i != n-1)
                Swap(i, j, i+1, j);
            // 좌우 swap
            if(j != n-1)
                Swap(i, j, i, j+1);

        }
    }

    cout << ans << '\n';

}

 

 

<algorithm> 라이브러리의 swap() 함수를 써서 푼것

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

int n;
char board[51][51];

int res = 0;

// 현재 보드에서 같은 색으로 이루어져 있는 가장 긴 연속부분의 길이를 반환한다
int Calculate() {
    // hor
    int hor_len = 1;
    for(int i = 0; i < n; i++) {
        char col = board[i][0];
        int len = 1;

        for(int j = 1; j < n; j++) {
            if(board[i][j] == col) {
                len++;
            }
            else {
                hor_len = max(hor_len, len);
                col = board[i][j];
                len = 1;
            }
        }
        hor_len = max(hor_len, len);
    }

    // ver
    int ver_len = 1;
    for(int i = 0; i < n; i++) {
        char col = board[0][i];
        int len = 1;

        for(int j = 1; j < n; j++) {
            if(board[j][i] == col) {
                len++;
            }
            else {
                ver_len = max(ver_len, len);
                col = board[j][i];
                len = 1;
            }
        }
        ver_len = max(ver_len, len);
    }

    return max(hor_len, ver_len);
}

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

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n-1; j++) {
            // 좌우
            swap(board[i][j], board[i][j+1]);
            res = max(res, Calculate());
            swap(board[i][j], board[i][j+1]); // 원상태로

            // 상하
            swap(board[j][i], board[j+1][i]);
            res = max(res, Calculate());
            swap(board[j][i], board[j+1][i]);
        }
    }

    cout << res;
}