백준 3085 c++"사탕 게임" -PlusUltraCode-

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

[필자 사고]

구현문제다.

N의 크기를 보았을 때 50으로 시간복잡도 측면에서 널널했다.

문제에서 요구하는 거는 인접한 두 캔디다. 

조심하자 필자는 처음에 무작이 캔디 2개인줄 알았다.

 

문제에서 주어진 조건에 맞게 코드를 짜면 문제없이 해결할 수 있다.

[코드 해설]

Input

• 입력으로 보드의 크기 N을 받는다.
• arr를 N x N 크기의 2차원 벡터로 초기화한다.
• 이어서 각 행에 대한 문자열을 입력받아 arr에 한 글자씩 저장한다.
• 이 과정을 통해 보드 상태가 준비된다.

---

swapCandy

• 보드에서 두 좌표 (i,k)와 (j,t)에 있는 사탕을 서로 교환한다.
• 교환은 임시 변수 temp를 사용하여 단순히 두 문자를 바꾼다.
• 스왑 이후 다시 원래 상태로 돌릴 수 있도록 Game_Start에서 교환-검사-복구 패턴으로 사용된다.

---

checkLine

• 현재 보드 상태에서 가장 긴 연속된 같은 색 사탕의 개수를 계산한다.
• 가로 검사: 각 행을 순회하며 인접한 두 칸이 같으면 count를 증가시킨다. 다르면 maxCount를 갱신하고 count를 다시 1로 초기화한다. 마지막 칸까지 검사한 후에도 최댓값을 갱신한다.
• 세로 검사: 각 열을 순회하며 위와 동일한 로직으로 연속 구간의 길이를 센다.
• 전체 과정에서 maxCount는 지금까지 발견된 가장 긴 같은 색 구간의 길이로 갱신된다.

---

Game_Start

• 보드의 모든 좌표 (i,k)를 시작점으로 하여, 인접한 칸과 교환을 시도한다.
• 두 가지 경우만 고려한다:
  1. 오른쪽 칸 (i, k+1)과 교환 (경계 조건 체크 포함).
  2. 아래 칸 (i+1, k)과 교환 (경계 조건 체크 포함).
• 각 교환 후에는 checkLine을 호출해 현재 보드에서 가장 긴 연속 구간 길이를 계산한다.
• 검사 후에는 다시 swapCandy를 호출해 보드를 원래 상태로 되돌린다.
• 모든 교환 시도를 마친 뒤, 전체 탐색 과정에서 구한 최대 길이 maxCount를 출력한다.

---

main

• 입출력 속도를 최적화하는 설정을 한 뒤,
• Input을 호출하여 보드를 입력받고,
• Game_Start를 호출하여 최대 사탕 연속 길이를 계산해 출력한다.

[소스 코드]

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

int N;
vector<vector<char>> arr;
int maxCount = -1;

void Input() {
    cin >> N;
    arr.assign(N, vector<char>(N));

    for (int i = 0; i < N; i++) {
        string str;
        cin >> str;
        for (int k = 0; k < str.size(); k++) {
            arr[i][k] = str[k];
        }
    }
}

void swapCandy(int i, int k, int j, int t) {
    char temp = arr[i][k];
    arr[i][k] = arr[j][t];
    arr[j][t] = temp;
}

void checkLine() {
    // 가로 검사
    for (int i = 0; i < N; i++) {
        int count = 1;
        for (int k = 0; k < N - 1; k++) {
            if (arr[i][k] == arr[i][k + 1]) {
                count++;
            }
            else {
                maxCount = max(maxCount, count);
                count = 1;
            }
        }
        maxCount = max(maxCount, count);
    }

    // 세로 검사
    for (int k = 0; k < N; k++) {
        int count = 1;
        for (int i = 0; i < N - 1; i++) {
            if (arr[i][k] == arr[i + 1][k]) {
                count++;
            }
            else {
                maxCount = max(maxCount, count);
                count = 1;
            }
        }
        maxCount = max(maxCount, count);
    }
}

void Game_Start() {
    for (int i = 0; i < N; i++) {
        for (int k = 0; k < N; k++) {
            
            if (k + 1 < N) {
                swapCandy(i, k, i, k + 1);
                checkLine();
                swapCandy(i, k, i, k + 1); 
            }
          
            if (i + 1 < N) {
                swapCandy(i, k, i + 1, k);
                checkLine();
                swapCandy(i, k, i + 1, k);
            }
        }
    }

    cout << maxCount << "\n";
}

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

    Input();
    Game_Start();
}