/ BOJ

BOJ_3085_사탕게임_JAVA

문제 : 사탕게임

링크 : BOJ_3085_사탕게임

접근 방식

문제가 설명하고자 하는 내용 중, 사탕을 서로 교환하는 내용은 옛날에 유행하던 게임 애니팡을 생각하면 직관적으로 다가갈 수 있다.

먼저, 인접한 서로 다른 사탕을 찾는다. 이는 가로도 될 수 있고 세로도 될 수 있다. 그 후, 두 개의 사탕의 위치를 서로 바꾸고, 행열을 탐색하여 같은 사탕으로 연속된 가장 긴 길이를 저장한다. 가장 긴 길이를 저장했다면, 사탕의 위치를 원래대로 돌려놓고 다음 인접한 서로 다른 사탕을 찾는다.

이것을 행열이 끝날때까지 반복한 후, 저장된 같은 사탕의 연속된 길이를 출력한다.

풀이 방법

  1. N값을 입력받아 N*N만큼 char 2차원 배열을 생성한다.

  2. 생성한 배열에 주어진 사탕의 정보를 입력한다.

  3. 배열을 먼저 열 기준으로 비교하여 인접한 사탕을 찾는다.

  4. 인접한 사탕을 찾은 후에는, 서로 자리를 바꾼다.

  5. 2차원배열을 순회하며 가장 연속된 사탕 수 중 가장 큰 값을 전역변수 max에 저장한다.

  6. 바꾼 사탕의 위치를 원래 자리로 돌려놓는다.

  7. 행을 기준으로 위의 작업을 한 번 더 반복한다.

  8. 저장되어있는 연속된 사탕의 개수의 최댓값을 출력한다.

소스 코드


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

public class BOJ_3085_사탕게임 {

	static char[][] arr;
	static int max;
	static int N;

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

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

		N = Integer.parseInt(in.readLine());

		arr = new char[N][N];

		for (int i = 0; i < N; i++) {
			arr[i] = in.readLine().toCharArray();
		}

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N - 1; j++) {
				if (arr[i][j] == arr[i][j + 1]) {
					continue;
				}
				char temp = arr[i][j];
				arr[i][j] = arr[i][j + 1];
				arr[i][j + 1] = temp;

				mapCheck();

				temp = arr[i][j];
				arr[i][j] = arr[i][j + 1];
				arr[i][j + 1] = temp;

			}
		}

		for (int j = 0; j < N; j++) {
			for (int i = 0; i < N - 1; i++) {
				if (arr[i][j] == arr[i + 1][j]) {
					continue;
				}
				char temp = arr[i][j];
				arr[i][j] = arr[i + 1][j];
				arr[i + 1][j] = temp;

				mapCheck();

				temp = arr[i][j];
				arr[i][j] = arr[i + 1][j];
				arr[i + 1][j] = temp;

			}
		}
		System.out.println(max);
	}

	public static void mapCheck() {
		int cnt = 1;
		for (int i = 0; i < N; i++) {
			cnt = 1;
			for (int j = 0; j < N - 1; j++) {
				if (arr[i][j] == arr[i][j + 1]) {
					cnt++;
				} else {
					max = Math.max(max, cnt);
					cnt = 1;
				}
			}
			max = Math.max(max, cnt);
		}
		max = Math.max(max, cnt);

		for (int j = 0; j < N; j++) {
			cnt = 1;
			for (int i = 0; i < N - 1; i++) {
				if (arr[i][j] == arr[i + 1][j]) {
					cnt++;

				} else {
					max = Math.max(max, cnt);
					cnt = 1;
				}
			}
			max = Math.max(max, cnt);
		}
		max = Math.max(cnt, max);

	}
}