백준: 사탕게임(3085)

알고리즘 문제 해결 과정을 기록합니다

September 26, 2025 · 3 min read

문제 개요 #

Source: 백준 링크
Difficulty: Silver 2
Key Concept: 구현

접근 방법 #

문자열을 입력 받아 서로 다른 색상의 사탕 2개의 위치를 교체 후 열 또는 행으로 동일한 색상만큼 먹을 수 있다고 했을 때, 최대한 많이 먹을 수 있는 양을 구하는 문제입니다. 입력받은 문자열에서 서로 다른 색의 사탕을 swap 후 전체 사탕에서 동일한 사탕이 행 또는 열로 얼마나 길게 연속되어 있는지 구하는 접근을 하였습니다.

시행착오 #

먼저 문제에서 swap을 얼마나 반복하고 사탕을 먹는 행위가 얼마나 반복되는지 명시되어 있지 않았습니다. 즉 이번 문제는 한 번만 바꾸고 한 번만 연속된 길이를 재어 그 값을 리턴하는 문제입니다. 문제를 꼼꼼히 읽지 않고 당연하게 반복된다는 생각으로 문제를 접근하여 문제를 제대로 풀지 못하였습니다. 코딩 테스트 문제의 시작과 끝은 문제를 정확하고 옳바르게 이해하는것이 시작이자 끝임을 되새겼습니다.

해결 방법 #

int n;
char board[50][50];
int answer = 0;

int getSameCandiesNumber() {
    int max_value = 1;
    // 행
    for (int r = 0; r < n; r++) {
        int cur = 1;
        for (int c = 1; c < n; c++) {
            if (board[r][c] != board[r][c - 1]) {
                max_value = std::max(cur, max_value);
                cur = 1;
            } else {
                cur++;
            }
        }
        max_value = std::max(cur, max_value);
    }
    for (int c = 0; c < n; c++) {
        int cur = 1;
        for (int r = 1; r < n; r++) {
            if (board[r][c] != board[r - 1][c]) {
                max_value = std::max(cur, max_value);
                cur = 1;
            } else {
                cur++;
            }
        }
        max_value = std::max(cur, max_value);
    }
    return max_value;
}


int solution() {
    // 여기에 문제 풀이 코드를 작성하세요.
    std::cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            std::cin >> board[i][j];
        }
    }

    answer = std::max(getSameCandiesNumber(), answer);

    for (int i = 0; i < n ; i++) {
        for (int j = 0; j < n; j++) {
            if (i + 1 < n && board[i][j] != board[i + 1][j]) {
                std::swap(board[i][j], board[i + 1][j]);
                answer = std::max(getSameCandiesNumber(), answer);
                std::swap(board[i][j], board[i + 1][j]);
            }
            if (j + 1 < n && board[i][j] != board[i][j + 1]) {
                std::swap(board[i][j], board[i][j + 1]);
                answer = std::max(getSameCandiesNumber(), answer);
                std::swap(board[i][j], board[i][j + 1]);
            }
        }
    }
    return answer;
}

알고리즘 설명 #

먼저 해당 문제는 색이 서로 다르면서 인접한 2개의 사탕의 탐색부터 시작됩니다. for문을 통해 전체 사탕에 대해 모두 탐색하되 행 또는 열방향으로 인접하므로 마지막 사탕 이전까지 간 다음 그 다음 사탕과 색상을 비교시켰습니다. 비교 이후 std::swap을 통해 2개의 사탕의 위치를 변경한 뒤 변경 시 연속된 사탕의 최대 개수를 구할 수 있는 getSameCandiesNumber()를 호출하도록 하였습니다. 행과 열 방향으로 탐색을 이어가면서 색이 같다면 수를 올려 개수를 파악하고, 사탕이 변경되면 현재 세고 있는 사탕의 수와 기존 기록해두었던 연속된 사탕의 최대 개수를 비교하여 큰 값을 최대 개수로 할당시켰습니다. 이후 행 또는 열이 끝날 때마다 최대 개수를 비교하여 최대 개수를 갱신하고 getSameCandiesNumber()함수가 최종적으로 리턴한 최대 개수를 또 다시 다른 위치의 사탕을 비교하였을 때의 기존 최대값과 비교하여 연속된 사탕의 최대 개수를 갱신시켰습니다. 여러 위치들에 대해서 갱신해야 하므로 한 번 갱신 이후 다시 std::swap을 통해 사탕의 위치를 원복시켜두었습니다.

성능 분석 #

Time Complexity: $O(N^4)$

핵심 정리 #

단순 구현 문제였지만 문제를 꼼꼼히 읽지 않아 생각보다 시간이 많이 걸린 문제였습니다. 문제의 의도를 더욱 정확히 파악하기 위해 문제 읽는 시간을 더욱 할애하여 정확한 이해를 바탕으로 코드를 작성해야 할 필요를 느꼈습니다.