링크
https://www.acmicpc.net/problem/3085
문제 설명
(정답률 33.254%)
상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다.
가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.
사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.
입력 예제
3
CCP
CCP
PPC
출력 예제
3
정답 코드
- 행과 열을 구분하여 기능을 구현
- 행(열)의 이웃 원소가 다를 경우 원소를 바꾼다.
- 2차원 배열의 연속되는 원소의 개수를 구하는 메소드 구현
- 원소의 위치를 이동할 때마다 위 메소드를 실행하여 최대값을 구한다.
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
System.setIn(new FileInputStream("src/input.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
String[][] board = new String[n][n];
String[][] tempArray = new String[n][n]; //원본 배열
int answer = 0;
//board 생성
for (int i = 0; i < n; i++) {
String[] input = br.readLine().split("");
for (int j = 0; j < n; j++) {
board[i][j] = input[j];
tempArray[i][j] = input[j];
}
}
String temp;
int cnt;
//행 기준 사탕 이동
for (int i = 0; i < n; i++) {
for (int j = 0; j < n - 1; j++) {
//이웃 원소가 다를 경우 위치 바꿈
if (!board[i][j].equals(board[i][j + 1])) {
temp = board[i][j];
board[i][j] = board[i][j + 1];
board[i][j + 1] = temp;
//카운트 메소드 실행
//이전 값보다 클 경우 answer에 할당
cnt = countMaxCandy(board, n);
if (answer < cnt) {
answer = cnt;
}
}
//board배열을 원래 배열로 초기화
for (int k = 0; k < n; k++) {
board[k] = tempArray[k].clone();
}
}
}
//열 기준 사탕 이동
for (int j = 0; j < n; j++) {
for (int i = 0; i < n - 1; i++) {
if (!board[i][j].equals(board[i + 1][j])) {
temp = board[i][j];
board[i][j] = board[i + 1][j];
board[i + 1][j] = temp;
cnt = countMaxCandy(board, n);
if (answer < cnt) {
answer = cnt;
}
}
for (int k = 0; k < n; k++) {
board[k] = tempArray[k].clone();
}
}
}
System.out.println(answer);
}
//2차원 배열에서 연속되는 원소를 카운트하는 메소드
public static int countMaxCandy(String[][] board, int boardSize) {
int rowCount = 1;
int colCount = 1;
int maxCnt = 0;
//열 기준 카운트
for (int i = 0; i < boardSize; i++) {
for (int j = 0; j < boardSize - 1; j++) {
if (board[i][j].equals(board[i][j + 1])) {
rowCount++;
if (maxCnt < rowCount) {
maxCnt = rowCount;
}
}
//이웃 원소끼리 다를 경우 변수 초기화
else {
rowCount = 1;
}
}
rowCount = 1;
}
//행 기준 카운트
for (int j = 0; j < boardSize; j++) {
for (int i = 0; i < boardSize - 1; i++) {
if (board[i][j].equals(board[i + 1][j])) {
colCount++;
if (maxCnt < colCount) {
maxCnt = colCount;
}
} else {
colCount = 1;
}
}
colCount = 1;
}
return maxCnt;
}
}정리
브루트 포스 문제였다. 즉, 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져온다. 이 알고리즘의 강력한 점은 예외 없이 100%의 확률로 정답만을 출력한다.
2차원 배열을 가지고 노는 문제여서 쉽지는 않았다.
행과 열을 동시에 원소를 이동시키는 것은 어려울 거 같아서
행과 열로 분리해서 구현하였다.
원소의 이동은 한 번이였기 때문에 이동할 때 마다 배열을 초기화하여야 했는데
단순히 배열을 할당하니까 초기화가 되지 않았다.
//배열을 복사하는 것이 아니라
//tempArray의 주소를 복사한다
board = tempArray;위와 같이 복사하는 것을 얕은 복사라 한다.
나는 두 배열을 독릭접으로 사용해야 했어서
깊은 복사를 했어야 했다.
//새로운 메모리 공간에 값을 복사
board = tempArray.clone();하지만 이 방법도 2차원 배열에선 되지 않아서
행 마다 clone 메소드를 실행하여야 했다.
for (int k = 0; k < n; k++) {
board[k] = tempArray[k].clone();
}참고
백엔드