백준: 3085 사탕 게임

문제

3085번: 사탕 게임

 

문제 풀이

인접한 사탕을 swap 하고, 가로 세로에서 연속된 사탕의 개수를 체크하면 해당 문제를 풀 수 있다. 다음과 같은 경우의 수를 판단하여 문제를 접근하면 쉽게 해결할 수 있다. 또한 swap 되는 경우 모든 범위를 탐색하는 것이 아닌, swap 되는 영역만 탐색한다면 속도를 높일 수 있을 것 같다.

• 대각선은 인접한것으로 판단하지 않는다.
  • 즉, 가로 세로에 대한 swap만 처리하고 비교하면 된다.
• N의 크기가 50이므로 브루트 포스로 충분히 탐색 가능한 크기이다.
  • 인접한 사탕을 배열의 순차적으로 swap 하고 탐색하는 것을 반복하여 답을 찾을 수 있다.

코드

Python 코드

from sys import stdin


def check_length():
    h_max, v_max = 1, 1

    for i in range(n):
        horizontal, vertical = 1, 1
        for j in range(n - 1):
            # 가로 확인
            if candy[i][j] == candy[i][j + 1]:
                horizontal += 1
            else:
                h_max = \
                    horizontal if h_max < horizontal else h_max
                horizontal = 1
            # 세로 확인
            if candy[j][i] == candy[j + 1][i]:
                vertical += 1
            else:
                v_max = \
                    vertical if v_max < vertical else v_max
                vertical = 1

        h_max =\
            horizontal if h_max < horizontal else h_max
        v_max = \
            vertical if v_max < vertical else v_max

    return h_max if h_max > v_max else v_max


if __name__ == "__main__":
    n = int(stdin.readline())
    candy = [list(stdin.readline().rstrip()) for _ in range(n)]
    answer = 0
    for i in range(n):
        for j in range(n - 1):
            # 가로 swap
            candy[i][j], candy[i][j + 1] = candy[i][j + 1], candy[i][j]
            answer = max(answer, check_length())
            ret = check_length()
            answer = ret if answer < ret else answer
            candy[i][j], candy[i][j + 1] = candy[i][j + 1], candy[i][j]
            # 세로 swap
            candy[j][i], candy[j + 1][i] = candy[j + 1][i], candy[j][i]
            ret = check_length()
            answer = ret if answer < ret else answer
            candy[j][i], candy[j + 1][i] = candy[j + 1][i], candy[j][i]

    print(answer)

Java 코드

import java.util.Scanner;

public class Main {
    static int check_length(char[][] candy) {
        int n = candy.length;
        int h_max = 1;
        int v_max = 1;
        int ret = 0;

        for (int i = 0; i < n; i++) {
            int horizontal = 1;
            int vertical = 1;
            for (int j = 0; j < n - 1; j++) {
                if (candy[i][j] == candy[i][j + 1]) {
                    horizontal += 1;
                } else {
                    if (h_max < horizontal) {
                        h_max = horizontal;
                    }
                    horizontal = 1;
                }
            }

            for (int j = 0; j < n - 1; j++) {
                if (candy[j][i] == candy[j + 1][i]) {
                    vertical += 1;
                } else {
                    if (v_max < vertical) {
                        v_max = vertical;
                    }
                    vertical = 1;
                }
            }
            if (h_max < horizontal) {
                h_max = horizontal;
            }

            if (v_max < vertical) {
                v_max = vertical;
            }
        }

        ret = v_max;

        if (h_max > v_max)
            ret = h_max;

        return ret;
    }

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        char[][] candy = new char[n][n];
        int answer = 0;

        for (int i = 0; i < n; i++) {
            candy[i] = s.next().toCharArray();
        }
        char temp;
        int ret;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n - 1; j++) {
                temp = candy[i][j];
                candy[i][j] = candy[i][j + 1];
                candy[i][j + 1] = temp;
                ret = check_length(candy);
                if (answer < ret) {
                    answer = ret;
                }
                temp = candy[i][j];
                candy[i][j] = candy[i][j + 1];
                candy[i][j + 1] = temp;
                temp = candy[j][i];
                candy[j][i] = candy[j + 1][i];
                candy[j + 1][i] = temp;
                ret = check_length(candy);
                if (answer < ret) {
                    answer = ret;
                }
                temp = candy[j][i];
                candy[j][i] = candy[j + 1][i];
                candy[j + 1][i] = temp;
            }
        }
        System.out.println(answer);
    }
}

위와 같은 로직을 다른 언어를 사용한다면 시간 내에 통과할 수 있지만, 파이썬은 통과할 수 없으며 PyPy3를 사용하여야 한다.