백준 3085번 [사탕 게임](C++) -yes6686- 티스토리

백준 문제 풀이: 3085번 [사탕 게임]

---

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

문제 설명:

NxN 크기의 격자판에서 사탕의 색이 주어집니다. 인접한 두 칸의 사탕을 교환하여, 같은 색의 사탕이 가장 긴 연속 구간을 만드는 경우의 길이를 구하는 문제입니다. 교환은 한 번만 가능하며, 이후 가장 긴 연속 구간을 계산합니다.

---

문제 해결 코드

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

char c[51][51]; // 사탕의 색 배열
int dx[4] = { 0, 0, 1, -1 }; // 상하좌우 이동 배열
int dy[4] = { 1, -1, 0, 0 };

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < s.size(); j++) {
            c[i][j] = s[j];
        }
    }

    int ans = 0;

    // 각 칸에서 가능한 최대 연속 길이를 계산
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int cnt = 1;

            // 가로 연속 길이 계산
            for (int a = 1; a < n; a++) {
                if (c[i][a] == c[i][a - 1]) {
                    cnt++;
                    ans = max(ans, cnt);
                } else {
                    cnt = 1;
                }
            }

            // 세로 연속 길이 계산
            cnt = 1;
            for (int a = 1; a < n; a++) {
                if (c[a][j] == c[a - 1][j]) {
                    cnt++;
                    ans = max(ans, cnt);
                } else {
                    cnt = 1;
                }
            }

            // 인접한 칸과 사탕 교환 후 최대 길이 계산
            for (int k = 0; k < 4; k++) {
                int nx = i + dx[k];
                int ny = j + dy[k];

                // 범위를 벗어나면 무시
                if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
                
                // 동일한 색이라면 교환할 필요 없음
                if (c[i][j] == c[nx][ny]) continue;

                // 사탕 교환
                swap(c[i][j], c[nx][ny]);

                // 교환 후 가로 연속 길이 계산
                cnt = 1;
                for (int a = 1; a < n; a++) {
                    if (c[i][a] == c[i][a - 1]) {
                        cnt++;
                        ans = max(ans, cnt);
                    } else {
                        cnt = 1;
                    }
                }

                // 교환 후 세로 연속 길이 계산
                cnt = 1;
                for (int a = 1; a < n; a++) {
                    if (c[a][j] == c[a - 1][j]) {
                        cnt++;
                        ans = max(ans, cnt);
                    } else {
                        cnt = 1;
                    }
                }

                // 사탕 복구
                swap(c[i][j], c[nx][ny]);
            }
        }
    }

    cout << ans << '\n'; // 최대 연속 길이 출력
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명:

• 핵심 알고리즘: 가능한 모든 사탕 교환을 시도하며, 교환 후 가로와 세로 연속된 같은 색의 사탕 길이를 계산합니다.
• 구현 세부사항:
  • 사탕 교환 전후로 최대 연속 길이를 각각 계산하며, 그 중 최대값을 저장합니다.
  • 가로와 세로에 대해 별도로 연속 길이를 계산하여 결과에 반영합니다.
  • 모든 교환을 시도한 후 배열을 원래 상태로 복구합니다.
• 시간 복잡도 분석:
  • 격자의 크기가 N×N일 때, 최대 O(N²)개의 칸에서 각 칸에 대해 O(N)번의 길이 계산이 이루어져, 전체 시간 복잡도는 O(N³)입니다.

---

결과

입력된 격자에서 최대 연속 사탕 길이를 계산하여 출력합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!