[백준] 3085. 사탕 게임 (Java)

 

문제

3085번: 사탕 게임

 

알고리즘

브루트포스

 

풀이

모든 칸에 대해 오른 칸, 아래 칸에 대해 사탕을 교환할 수 있다면 교환하고 최댓값을 갱신한다.

(0,0) 부터 (N-1, N-1) 로 이동하기 때문에 왼 칸과 위 칸은 이미 이전에 검사를 하게 된다.

 

모든 칸에 대해 다음 작업을 수행한다.

1. 오른 칸이 범위 안에 있고, 사탕의 색이 다르다면

(1) 오른 칸과 사탕 교환

(2) 가장 긴 연속 부분 길이 확인 및 갱신

(3) 오른 칸과 사탕 교환 (원래대로 되돌려놓기 위함)

 

2. 아래 칸이 범위 안에 있고, 사탕의 색이 다르다면

(1) 아래 칸과 사탕 교환

(2) 가장 긴 연속 부분 길이 확인 및 갱신

(3) 아래 칸과 사탕 교환 (원래대로 되돌려놓기 위함)

---

가장 긴 연속 부분 길이 확인

 

각 행과 열에 대해 다음 작업을 진행한다.

1. 마지막 등장 사탕과 다른 사탕이 나오면

그동안 연속되었던 길이 count를 max값과 비교해 갱신하고, 마지막 등장 사탕을 현재 사탕으로, count를 1로 바꾼다.

2. 마지막 등장 사탕과 같은 사탕이 나오면 count를 1 증가시킨다.

 

코드 

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

public class Main {
	static int N;
	static char[][] board;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());
		board = new char[N][N];
		for (int i = 0; i < N; i++) {
			String str = br.readLine();
			for (int j = 0; j < N; j++) {
				board[i][j] = str.charAt(j);
			}
		}

		int max = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {

				if (j < N - 1 && board[i][j] != board[i][j+1]) {
					swap(i, j, i, j + 1);
					max = Math.max(max, count());
					swap(i, j, i, j + 1);
				}

				if (i < N - 1 && board[i][j] != board[i+1][j]) {
					swap(i, j, i + 1, j);
					max = Math.max(max, count());
					swap(i, j, i + 1, j);
				}
			}
		}

		System.out.println(max);
	}

	private static int count() {

		int max = 0;

		for (int i = 0; i < N; i++) {
			char c = board[i][0];
			int count = 1;

			for (int j = 1; j < N; j++) {
				if (board[i][j] != c) {
					max = Math.max(max, count);
					c = board[i][j];
					count = 1;
				}
				else count++;
			}

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

		for (int i = 0; i < N; i++) {
			char c = board[0][i];
			int count = 1;

			for (int j = 1; j < N; j++) {
				if (board[j][i] != c) {
					max = Math.max(max, count);
					c = board[j][i];
					count = 1;
				}
				else count++;
			}

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

		return max;
	}

	private static void swap(int y1, int x1, int y2, int x2) {
		char tmp = board[y1][x1];
		board[y1][x1] = board[y2][x2];
		board[y2][x2] = tmp;
	}

}