[BOJ/JAVA] 백준 3085 : 사탕 게임 (자바)

문제 정보

  문제명   - 사탕 게임
  난이도   - 실버 III
문제 번호 - 3085번

---

문제 링크

BOJ_S3_3085_사탕_게임

3085번: 사탕 게임

---

문제

상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다.
가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.
사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.

---

입력

첫째 줄에 보드의 크기 N이 주어진다. (3 ≤ N ≤ 50)
다음 N개 줄에는 보드에 채워져 있는 사탕의 색상이 주어진다. 빨간색은 C, 파란색은 P, 초록색은 Z, 노란색은 Y로 주어진다.
사탕의 색이 다른 인접한 두 칸이 존재하는 입력만 주어진다.

---

출력

첫째 줄에 상근이가 먹을 수 있는 사탕의 최대 개수를 출력한다.

---

예제 입력/출력

예제 출력

예제 입력	예제 출력
3 CCP CCP PPC	3
4 PPPP CYZY CCPY PPCC	4
5 YCPZY CYZZP CCPPP YCYZC CPPZZ	4

---

힌트

예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다.

---

알고리즘 분류

● 구현
● 브루트포스 알고리즘

---

소스코드

package Lv2_Silver;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
/**
 * @author HanHoon
 * @category 구현, 브루트포스 알고리즘
 * https://www.acmicpc.net/problem/3085
 */
public class BOJ_S3_3085_사탕_게임 {
	static int N, max; 
	static char[][] board;
	public static void cntCandy() {
		for (int i = 0; i < N; i++) {
			// 이전사탕 초기값
			char preCol = board[i][0];
			char preRow = board[0][i];
			// 세로cnt, 가로cnt
			int cntCol = 0, cntRow = 0;
			for (int j = 0; j < N; j++) {
				// (가로) 다음 사탕이 같다면 count 값 증가
				if(preCol == board[i][j])
					cntCol++;
				// (가로) 다음 사탕이 다르다면 count값 초기화 밑 사탕 정보 저장
				else {
					preCol = board[i][j];
					cntCol = 1;
				}
				// (세로) 다음 사탕이 같다면 count 값 증가
				if(preRow == board[j][i])
					cntRow++;
				// (세로) 다음 사탕이 다르다면 count값 초기화 밑 사탕 정보 저장
				else {
					preRow = board[j][i];
					cntRow = 1;
				}
				// 가로든 세로든 최대값 최신화
				max = Math.max(max, cntCol);
				max = Math.max(max, cntRow);
			}
		}
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		// NxN 크기의 보드
		N = Integer.parseInt(br.readLine());
		board = new char[N][];
		// 보드 값 입력
		for (int i = 0; i < N; i++) {
			board[i] = br.readLine().toCharArray();
		}
		// 초기값
		max = Integer.MIN_VALUE;
		// 아무것도 하지 않았을때 먹을 수 있는 사탕 최대 개수
		cntCandy();
		// 하, 우
		int[] dRow = { 1, 0};
		int[] dCol = { 0, 1};
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				// 아래쪽과 바꾼 경우, 오른쪽을 바꾼경우
				for (int index = 0; index < 2; index++) {
					int changeRow = i + dRow[index];
					int changeCol = j + dCol[index];
					// 범위를 벗어나면 continue
					if(changeRow < 0 || changeRow >= N || changeCol < 0 || changeCol >= N)
						continue;
					// 값을 변경하고 cntCandy() 실행
					char tmp = board[i][j];
					board[i][j] = board[changeRow][changeCol];
					board[changeRow][changeCol] = tmp;
					cntCandy();
					// 값 복구
					tmp = board[i][j];
					board[i][j] = board[changeRow][changeCol];
					board[changeRow][changeCol] = tmp;
				}
			}
		}
		System.out.println(max);
		br.close();
	}
}

 

---

BaekJoon List

BaekJoon List

---

  

기회는 준비된 자에게 찾아온다.

 

---