[백준3085] 사탕 게임 - 자바(JAVA)

1. 문제

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

3085번: 사탕 게임

 

2. 풀이

브루트포스 알고리즘을 사용해서 문제를 풀었다.

먼저 사탕을 교환하는 모든 경우의 수를 구현하였다.

여기서 중요한 점은

만약 (i, j)와 (i+1, j) 사탕을 교환했다면 즉, 위아래 사탕을 교환했다면 `i행, i+1행, j열`을 검사해서 얻을 수 있는 최대 사탕 갯수를 구해주었다.

(i, j)와 (i, j+1) 사탕을 교환했다면 즉, 좌우 사탕을 교환했다면 `j열, j+1열, i행`을 검사해서 얻을 수 있는 최대 사탕 갯수를 구해주었다.

 

행과 열에서 최대 사탕 갯수를 구해주는 함수는 각각 check_row(), check_col()이다.

 

3. 코드

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

public class Main {

	static int n, result;
	static char[][] map;

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

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		n = Integer.parseInt(br.readLine());
		map = new char[n][n];

		for (int i = 0; i < n; i++) {
			String input = br.readLine();
			for (int j = 0; j < n; j++) {
				map[i][j] = input.charAt(j);
			}
		}

		result = 0;

		for (int i = 0; i < n; i++) {

			for (int j = 0; j < n - 1; j++) {
				swap_col(i, j);
				check_col(j);
				check_col(j + 1);
				check_row(i);
				swap_col(i, j);

				swap_row(j, i);
				check_row(j);
				check_row(j + 1);
				check_col(i);
				swap_row(j, i);
			}
		}

		System.out.println(result);

	}

	public static void swap_row(int row, int col) {
		char tmp = map[row][col];
		map[row][col] = map[row + 1][col];
		map[row + 1][col] = tmp;
	}

	public static void swap_col(int row, int col) {
		char tmp = map[row][col];
		map[row][col] = map[row][col + 1];
		map[row][col + 1] = tmp;
	}

	public static void check_row(int row) {
		int prev = map[row][0];
		int max = 1;
		int cnt = 1;
		for (int i = 1; i < n; i++) {
			int cur = map[row][i];
			if (cur == prev) {
				cnt++;
				max = Math.max(max, cnt);
			} else {
				max = Math.max(max, cnt);
				cnt = 1;
			}
			prev = cur;
		}

		result = Math.max(result, max);
	}

	public static void check_col(int col) {
		int prev = map[0][col];
		int max = 1;
		int cnt = 1;
		for (int i = 1; i < n; i++) {
			int cur = map[i][col];
			if (cur == prev) {
				cnt++;
				max = Math.max(max, cnt);
			} else {
				max = Math.max(max, cnt);
				cnt = 1;
			}
			prev = cur;
		}

		result = Math.max(result, max);
	}

}