[백준] 3085 - 사탕 게임

1. 문제

3085번: 사탕 게임

2. 개요

N x N 크기의 보드에 사탕이 채워져 있다.

사탕의 색이 서로 다른 인접한 두 칸을 골라 사탕을 교환한다.

이후 모두 같은 색으로 이루어진 가장 긴 연속 부분 (행, 열)을 골라 그 사탕을 모두 먹는다.

이 때 먹을 수 있는 사탕의 최대 개수를 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

사탕을 가로, 세로로 교환하는 함수를 각각 만들어둔다.

또한 가장 긴 연속 부분을 찾는 함수 (체크) 를 구현해둔다.

보드의 모든 부분을 탐색하면서 가로교환 - 체크 - 가로교환(원상복구), 세로교환 - 체크 - 세로교환(원상복구)를 진행하며 답을 갱신한다.

모든 위치에 대해 탐색이 완료되었다면 답을 출력한다.

3-2. Python

import sys

N = int(sys.stdin.readline())

board = []

answer = 1

for i in range(N):
    board.append(list(sys.stdin.readline().rstrip()))

def changehor(y, x):
    if x >= N - 1:
        return

    board[y][x], board[y][x + 1] = board[y][x + 1], board[y][x]

def changever(y, x):
    if y >= N - 1:
        return

    board[y][x], board[y + 1][x] = board[y + 1][x], board[y][x]

def chk():
    global answer
    for i in range(N):
        a, b = 1, 1
        for j in range(1, N):
            if board[i][j] == board[i][j - 1]:
                a += 1
            
            else:
                answer = max(answer, a)
                a = 1

            if board[j][i] == board[j - 1][i]:
                b += 1

            else:
                answer = max(answer, b)
                b = 1

        answer = max(answer, a, b)

for i in range(N):
    for j in range(N):
        changehor(i, j)
        chk()
        changehor(i, j)
        changever(i, j)
        chk()
        changever(i, j)

print(answer)

3-3. C#

namespace boj_3085
{
    internal class Program
    {
        static char[,] board;
        static int N;
        static int answer;

        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

            N = int.Parse(sr.ReadLine());

            answer = 1;

            board = new char[N, N];

            for (int i = 0; i < N; i++)
            {
                string row = sr.ReadLine().TrimEnd();

                for (int j = 0; j < N; j++)
                {
                    board[i, j] = row[j];
                }
            }

            for (int i = 0; i < N; i++)
            {
                for (int j = 0; j < N; j++)
                {
                    changehor(i, j);
                    chk();
                    changehor(i, j);
                    changever(i, j);
                    chk();
                    changever(i, j);
                }
            }

            sw.WriteLine(answer);
            sw.Close();
        }

        static void changehor(int y, int x)
        {
            if (x >= N - 1)
                return;

            char tmp = board[y, x];
            board[y, x] = board[y, x + 1];
            board[y, x + 1] = tmp;
        }

        static void changever(int y, int x)
        {
            if (y >= N - 1)
                return;

            char tmp = board[y, x];
            board[y, x] = board[y + 1, x];
            board[y + 1, x] = tmp;
        }

        static void chk()
        {
            for (int i = 0; i < N; i++)
            {
                int a = 1;
                int b = 1;

                for (int j = 1; j < N; j++)
                {
                    if (board[i, j] == board[i, j - 1])
                        a++;

                    else
                    {
                        answer = (int)MathF.Max(answer, a);
                        a = 1;
                    }

                    if (board[j, i] == board[j - 1, i])
                        b++;

                    else
                    {
                        answer = (int)MathF.Max(answer, b);
                        b = 1;
                    }
                }

                answer = (int)MathF.Max(MathF.Max(answer, a), b);
            }
        }
    }
}