[Baekjoon] 3085_사탕 게임

Silver II

문제(출처: https://www.acmicpc.net/problem/3085)

---

< 사탕 게임 >

 

문제 풀이 

 

모든 경우의 사탕의 색이 다른 인접한 두 칸을 교환한다. 교환한 후 같은 색으로 이루어져 있는 가장 긴 연속 부분을 고른다.

 

 

 my solution (Java)

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

public class _3085_ { // 사탕 게임
	static char arr[][];
	static int n, max;
	static int dx[] = { 1, 0 };
	static int dy[] = { 0, 1 };

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

		n = Integer.parseInt(bf.readLine());

		arr = new char[n][n];
		max = 0;

		for (int i = 0; i < n; i++) {
			String str = bf.readLine();
			for (int j = 0; j < n; j++) {
				arr[i][j] = str.charAt(j);
			}
		}

		candy();

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				change(i, j);
			}
		}
		System.out.println(max);
	}

	private static void change(int x, int y) {
		for (int i = 0; i < 2; i++) {
			int a = x + dx[i];
			int b = y + dy[i];

			if (a >= 0 && a < n && b >= 0 && b < n && arr[x][y] != arr[a][b]) {
				char tempx = arr[x][y];
				char tempy = arr[a][b];

				arr[x][y] = tempy;
				arr[a][b] = tempx;

				candy();

				arr[x][y] = tempx;
				arr[a][b] = tempy;
			}
		}

	}

	private static void candy() {
		char x, y;
		int cnt1, cnt2;

		for (int i = 0; i < n; i++) {
			x = arr[i][0];
			y = arr[0][i];
			cnt1 = 1;
			cnt2 = 1;
			for (int j = 1; j < n; j++) {
				if (arr[i][j] == x) {
					cnt1 += 1;
				} else {
					if (max < cnt1) {
						max = cnt1;
					}
					x = arr[i][j];
					cnt1 = 1;
				}

				if (arr[j][i] == y) {
					cnt2 += 1;
				} else {
					if (max < cnt2) {
						max = cnt2;
					}
					y = arr[j][i];
					cnt2 = 1;
				}
			}
			if (max < cnt1) {
				max = cnt1;
			}
			if (max < cnt2) {
				max = cnt2;
			}
		}
	}
}

변수)
n : 보드의 크기
arr : 보드 정보
max : 먹을 수 있는 사탕의 최대 개수

 

보드의 정보를 입력받은 후 candy 함수를 호출해 사탕을 교환하지 않은 상태에서 먹을 수 있는 사탕의 최대 개수를 구한다. 보드를 탐색하며 사탕을 교환할 수 있는 경우를 찾기 위해 change 함수를 호출한다. 최종 먹을 수 있는 사탕의 최대 개수인 max를 출력한다.

 

change (좌표)

현재 좌표의 아래와 오른쪽을 탐색하여 보드 범위 안이고, 사탕의 색이 다르다면 사탕을 교환한다. 그 후 사탕의 최대 개수를 구하기 위해 candy 함수를 호출한다.

 

candy

각각 행 탐색, 열 탐색을 통해 먹을 수 있는 사탕의 최대 개수를 구한다.

---

---