[백준 3085 / JAVA] 사탕 게임

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

3085번: 사탕 게임

 

처음에는 이게 브루트포스로 다 하는게 맞나 싶은 문제였다.

 

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (j + 1 < N && n[i][j] != n[i][j + 1]) {
                    // 오른쪽 값과 바꾼 후
                    swap(n, i, j, i, j + 1);
                    result = sol(n); // 사탕 수 구하기
                    if (result > max)
                        max = result;
                    // 다시 복구
                    swap(n, i, j, i, j + 1);
                }
                if (i + 1 < N && n[i][j] != n[i + 1][j]) {
                    //아래 값과 바꿈
                    swap(n, i, j, i + 1, j);
                    result = sol(n);
                    if (result > max)
                        max = result;
                    swap(n, i, j, i + 1, j);
                }
            }
        }

오른쪽과 아래의 존재하는 값과 바꿔가며 사탕 수를 구한다.

왼쪽과 위에 존재하는 값과는 바꿀 필요가 없다.

 

    public static int sol(String[][] n) {
        int row, col, result = 1;
        for (int i = 0; i < N; i++) {
            row = 1; //행(가로)
            col = 1; //열(세로)
            for (int j = 1; j < N; j++) {
                if (n[i][j].equals(n[i][j - 1]))
                    row++;
                else
                    row = 1;
                if (n[j][i].equals(n[j - 1][i]))
                    col++;
                else
                    col = 1;
                if (row > result)
                    result = row;
                if (col > result)
                    result = col;
            }
        }
        return result;
    }

사탕 수를 구하는 메서드이다.

행과 열을 동시에 구한다. 같을 경우 값을 더하고 아닐 경우 1로 초기화 해준다.

 

전체코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static String[][] n;
    static int N;

    public static void main(String[] args) throws IOException {

        String input;
        int result, max = 0;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        n = new String[N][N];

        for (int i = 0; i < N; i++) {
            input = br.readLine();
            n[i] = input.split("");
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (j + 1 < N && n[i][j] != n[i][j + 1]) {
                    // 오른쪽 값과 바꾼 후
                    swap(n, i, j, i, j + 1);
                    result = sol(n); // 사탕 수 구하기
                    if (result > max)
                        max = result;
                    // 다시 복구
                    swap(n, i, j, i, j + 1);
                }
                if (i + 1 < N && n[i][j] != n[i + 1][j]) {
                    //아래 값과 바꿈
                    swap(n, i, j, i + 1, j);
                    result = sol(n);
                    if (result > max)
                        max = result;
                    swap(n, i, j, i + 1, j);
                }
            }
        }
        System.out.println(max);
    }

    public static int sol(String[][] n) {
        int row, col, result = 1;
        for (int i = 0; i < N; i++) {
            row = 1; //행(가로)
            col = 1; //열(세로)
            for (int j = 1; j < N; j++) {
                if (n[i][j].equals(n[i][j - 1]))
                    row++;
                else
                    row = 1;
                if (n[j][i].equals(n[j - 1][i]))
                    col++;
                else
                    col = 1;
                if (row > result)
                    result = row;
                if (col > result)
                    result = col;
            }
        }
        return result;
    }

    public static void swap(String[][] n, int x1, int y1, int x2, int y2) {
        String temp = n[x1][y1];
        n[x1][y1] = n[x2][y2];
        n[x2][y2] = temp;
    }
}