[백준 3085] 사탕 게임 (C#, C++) - soo:bak

문제 링크

3085번 - 사탕 게임

설명

N×N 크기의 보드에 C, P, Z, Y 네 가지 색상의 사탕이 채워져 있는 상황에서, N (3 ≤ N ≤ 50)과 보드의 상태가 주어질 때, 인접한 두 칸을 한 번 교환한 후 같은 색으로 이루어진 가장 긴 연속 부분(행 또는 열)의 최대 길이를 구하는 문제입니다.

접근법

문제를 해결하기 위해 가능한 모든 교환을 시도한 후 각 경우마다 최대 연속 길이를 확인합니다.

N이 최대 50이므로 완전 탐색이 가능합니다.

인접한 두 칸은 가로로 인접(i, j)와 (i, j+1) 또는 세로로 인접(i, j)와 (i+1, j)입니다.

색이 다른 인접한 칸만 교환할 의미가 있으므로 이 경우만 확인합니다.

각 위치 (i, j)에서:

1. 오른쪽 칸 (i, j+1)과 색이 다르면 교환 → 보드 검사 → 복구
2. 아래쪽 칸 (i+1, j)과 색이 다르면 교환 → 보드 검사 → 복구

보드 검사는 모든 행과 열을 순회하며 같은 색이 연속되는 최대 길이를 찾습니다.

각 행에서 왼쪽부터 순회하며 이전 칸과 같은 색이면 카운트를 증가시키고, 다른 색이면 최댓값을 갱신하고 카운트를 1로 초기화합니다.

같은 방식으로 각 열도 확인합니다.

예를 들어 행이 “CPPCC”일 때:

• C (1개)
• C→P 다름 → 최댓값 갱신, P (1개)
• P→P 같음 → P (2개)
• P→C 다름 → 최댓값 갱신, C (1개)
• C→C 같음 → C (2개) 최댓값은 2입니다.

가능한 모든 교환의 개수는 최대 2 × N × N = 5,000개이고, 각 검사는 O(N²)이므로 전체 시간 복잡도는 O(N⁴)이지만 N ≤ 50이므로 충분히 통과할 수 있습니다.

---

Code

C#

using System;

namespace Solution {
  class Program {
    static int n;
    static char[,] board = new char[50, 50];
    static int best = 1;

    static void Check() {
      for (var i = 0; i < n; i++) {
        var cnt = 1;
        for (var j = 1; j < n; j++) {
          if (board[i, j] == board[i, j - 1]) cnt++;
          else { best = Math.Max(best, cnt); cnt = 1; }
        }
        best = Math.Max(best, cnt);
      }

      for (var j = 0; j < n; j++) {
        var cnt = 1;
        for (var i = 1; i < n; i++) {
          if (board[i, j] == board[i - 1, j]) cnt++;
          else { best = Math.Max(best, cnt); cnt = 1; }
        }
        best = Math.Max(best, cnt);
      }
    }

    static void Main(string[] args) {
      n = int.Parse(Console.ReadLine()!);

      for (var i = 0; i < n; i++) {
        var line = Console.ReadLine()!;
        for (var j = 0; j < n; j++)
          board[i, j] = line[j];
      }

      for (var i = 0; i < n; i++) {
        for (var j = 0; j < n; j++) {
          if (j + 1 < n && board[i, j] != board[i, j + 1]) {
            (board[i, j], board[i, j + 1]) = (board[i, j + 1], board[i, j]);
            Check();
            (board[i, j], board[i, j + 1]) = (board[i, j + 1], board[i, j]);
          }

          if (i + 1 < n && board[i, j] != board[i + 1, j]) {
            (board[i, j], board[i + 1, j]) = (board[i + 1, j], board[i, j]);
            Check();
            (board[i, j], board[i + 1, j]) = (board[i + 1, j], board[i, j]);
          }
        }
      }

      Console.WriteLine(best);
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef vector<string> vs;

int n;
vs board;
int best = 1;

void check() {
  for (int i = 0; i < n; i++) {
    int cnt = 1;
    for (int j = 1; j < n; j++) {
      if (board[i][j] == board[i][j - 1]) cnt++;
      else { best = max(best, cnt); cnt = 1; }
    }
    best = max(best, cnt);
  }

  for (int j = 0; j < n; j++) {
    int cnt = 1;
    for (int i = 1; i < n; i++) {
      if (board[i][j] == board[i - 1][j]) cnt++;
      else { best = max(best, cnt); cnt = 1; }
    }
    best = max(best, cnt);
  }
}

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

  cin >> n;
  board.resize(n);

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

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (j + 1 < n && board[i][j] != board[i][j + 1]) {
        swap(board[i][j], board[i][j + 1]);
        check();
        swap(board[i][j], board[i][j + 1]);
      }

      if (i + 1 < n && board[i][j] != board[i + 1][j]) {
        swap(board[i][j], board[i + 1][j]);
        check();
        swap(board[i][j], board[i + 1][j]);
      }
    }
  }

  cout << best << "\n";

  return 0;
}