[BOJ] 3085 사탕 게임

#include <stdio.h>

char candy[50][50];
int n;

void swap(char* a, char* b)
{
    char temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

int max(int a, int b)
{
    return a > b ? a : b;
}

int checkAll()
{
    int i, j, count;
    int MAX = -1;
    char before;

    for (i = 0; i < n; i++) {
        count = 1;
        before = candy[i][0];
        for (j = 1; j < n; j++) {
            if (candy[i][j] == before) {
                count++;
                MAX = max(MAX, count);
            }
            else {
                MAX = max(MAX, count);
                count = 1;
                before = candy[i][j];
            }
        }
    }
    for (j = 0; j < n; j++) {
        count = 1;
        before = candy[0][j];
        for (i = 1; i < n; i++) {
            if (candy[i][j] == before) {
                count++;
                MAX = max(MAX, count);
            }
            else {
                MAX = max(MAX, count);
                count = 1;
                before = candy[i][j];
            }
        }
    }

    return MAX;
}

int main(void)
{
    int i, j, k, count;
    int MAX = -1;
    char before;

    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        scanf("\n");
        for (j = 0; j < n; j++)
            scanf("%c", &candy[i][j]);
    }
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            if (j + 1 < n && candy[i][j] != candy[i][j + 1]) {
                swap(&candy[i][j], &candy[i][j + 1]);
                MAX = max(MAX, checkAll());
                swap(&candy[i][j], &candy[i][j + 1]);
            }
            if (i + 1 < n && candy[i][j] != candy[i + 1][j]) {
                swap(&candy[i][j], &candy[i + 1][j]);
                MAX = max(MAX, checkAll());
                swap(&candy[i][j], &candy[i + 1][j]);
            }
        }
    }
    printf("%d", MAX);

    return 0;
}

총 약 3시간

 

문제 이해와 첫 풀이에 걸린 시간은 9분인데 디버깅하다 잘못 이해했음을 알았다.
처음엔 같은 색의 서로 인접한 사탕의 수를 구한다고 생각해서 dfs로 풀었음. 예제 출력이 자꾸 5가 나와서 뭐지 하면서 다시 읽고 이해했다.
이렇게 다시 풀었던 코드가 엄청나다. 엄청나게... 쓸데없이 복잡하다. 현재 사탕과 자리를 바꾼 사탕 위치를 기준으로 상하좌우 각각 for문을 돌며 최대 길이를 구했다. main의 if문 안에 for문이 4개씩 들어갔지... for안에 for안에 if안에 for안에 if else if else... 풀면서도 분명 이거보다 깔끔한 방법이 있다는 것만은 확신했음.
그러고도 2시간 동안 4번의 틀렸습니다를 맞았다. 이 글을 보고 고려하지 않은 경우가 있다는 것, for문 4번 쓰는 대신 모든 사탕을 확인하면 된다는 것도 알았다.

 

이번 문제는 부주의함이 걸림돌이었다. 문제의 조건을 마음대로 착각하거나 실행 중에 변하는 부분에만 신경쓰는 일은 없어야겠다.