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

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

3085번: 사탕 게임

 

문제 해석

N x N 크기에 사탕이 채워져 있다.
사탕의 색은 같지 않을 수 있다.
사탕의 색이 다른 인접한 두 칸을 골라서 교환할 수 있다.
교환은 단 한 번만 이루어진다.
이때 사탕이 같은 색인 가장 긴 연속 부분을 출력한다.

 

입력

첫째 줄에 보드의 크기 N이 주어진다.

다음 N개의 줄에는 보드에 채워져 있는 사탕의 색상이 주어진다.

 

제약조건

3 <= N <= 50

빨간색은 C, 파란색은 P , 초록색은 Z, 노란색은 Y로 주어진다.

사탕의 색이 다른 인접한 두 칸이 존재하는 입력만 주어진다.

 

출력

이때 사탕이 같은 색인 가장 긴 연속 부분을 출력한다.

 

문제 풀이 전 설계

1. 부르트 포스(full scan)

인접한 칸의 사탕을 교환하고 최대 개수를 갱신한다.

사탕을 재위치시키고 다음 요소를 검사한다.

보드의 크기가 3이상 50 이하이기 때문에 완전 탐색을 해도 괜찮을 것 같다.

 

코드

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

/*
 * BOJ : 3085번 사탕 게임
 * N x N 크기에 사탕이 채워져 있다.
 * 사탕의 색은 같지 않을 수 있다.
 * 사탕의 색이 다른 인접한 두 칸을 골라서 교환할 수 있다.
 * 교환은 단 한번만 이루어진다.
 * 이때 사탕이 같은 색인 가장 긴 연속 부분을 출력한다.
 */
public class CandyGame {
	static int n;
	static char[][] candyBoard;
	// 위, 오른쪽, 아래, 왼쪽
	static int[] dy = { -1, 0, 1, 0 };
	static int[] dx = { 0, 1, 0, -1 };
	static int maxCandyCount;

	public static void main(String[] args) throws IOException {
		inputCandyInfo();
		searchMaxCandyCount();
		printMaxCandyCount();
	}

	private static void inputCandyInfo() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());

		candyBoard = new char[n][n];
		for (int i = 0; i < n; i++) {
			String str = br.readLine();
			for (int j = 0; j < str.length(); j++) {
				candyBoard[i][j] = str.charAt(j);
			}
		}
	}

	private static void searchMaxCandyCount() {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				for (int k = 0; k < 4; k++) {
					int tempY = i + dy[k];
					int tempX = j + dx[k];
					if(tempX < 0 || tempX >= n || tempY <0 || tempY >=n) {
						continue;
					}
					swap(i, j, tempY, tempX);
					countLongestCandy(i, j, tempY, tempX);
					//swap 되돌리기
					swap(i, j, tempY, tempX);				
				}
			}
		}
	}

	private static void swap(int i, int j, int tempY, int tempX) {
		char tempCandy = candyBoard[i][j];
		candyBoard[i][j] = candyBoard[tempY][tempX];
		candyBoard[tempY][tempX] = tempCandy;
	}

	private static void countLongestCandy(int i, int j, int tempY, int tempX) {
		// 바꿨을때 어느쪽이 최대인지 모르기 때문에 4번 검사해야 함.
		searchRow(i);
		searchRow(tempY);
		searchColumn(j);
		searchColumn(tempX);
	}

	private static void searchColumn(int fixedValue) {
		char temp = candyBoard[0][fixedValue];
		int tempMax = 1;
		for (int k = 1; k < n; k++) {
			if (candyBoard[k][fixedValue] == temp) {
				tempMax++;
			} else {
				temp = candyBoard[k][fixedValue];
				maxCandyCount = maxCandyCount > tempMax ? maxCandyCount : tempMax;
				tempMax = 1;
			}
		}
		maxCandyCount = maxCandyCount > tempMax ? maxCandyCount : tempMax;
	}

	private static void searchRow(int fixedValue) {
		int tempMax = 1;
		char temp = candyBoard[fixedValue][0];
		for (int k = 1; k < n; k++) {
			if (candyBoard[fixedValue][k] == temp) {
				tempMax++;
			} else {
				temp = candyBoard[fixedValue][k];
				maxCandyCount = maxCandyCount > tempMax ? maxCandyCount : tempMax;
				tempMax = 1;
			}
		}
		maxCandyCount = maxCandyCount > tempMax ? maxCandyCount : tempMax;
	}
	
	private static void printMaxCandyCount() throws IOException{
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		bw.write(maxCandyCount + "\n");
		bw.flush();
		bw.close();
	}

}

dx, dy 배열을 사용하여 하나의 요소에 대해 상하좌우를 탐색하여 교환합니다.

교환한 후에는 먹을 수 있는 사탕의 최댓값을 구한 후 다시 교환한 것을 되돌려 놓습니다.

이것을 첫요소부터 끝 요소까지 반복합니다.

 

countLongestCandy() 메서드는 교환된 값들의 사탕 최대길이를 모두 구합니다.

 

searchRow, searchColumn 메서드는 최대사탕길이를 탐색합니다.

반복문을 통해 연속된값이 나오면 tempMax를 증가시켜 연속 사탕 길이를 증가시키며 만약 다른 값이 나오게 되면

tempMax를 초기화시키며 최대 사탕 길이와 비교하여 큰 값을 넣어줍니다.