문제
상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다.
가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.
사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 보드의 크기 N이 주어진다. (3 ≤ N ≤ 50)
다음 N개 줄에는 보드에 채워져 있는 사탕의 색상이 주어진다. 빨간색은 C, 파란색은 P, 초록색은 Z, 노란색은 Y로 주어진다.
사탕의 색이 다른 인접한 두 칸이 존재하는 입력만 주어진다.
출력
첫째 줄에 상근이가 먹을 수 있는 사탕의 최대 개수를 출력한다.
예제 입력 1
3
CCP
CCP
PPC예제 출력 1
3예제 입력 2
4
PPPP
CYZY
CCPY
PPCC예제 출력 2
4예제 입력 3
5
YCPZY
CYZZP
CCPPP
YCYZC
CPPZZ예제 출력 3
4문제 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
public class Main {
static int[][] dir={{0,1},{0,-1},{1,0},{-1,0}};
static char[][] board;
static int N;
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
N=Integer.parseInt(br.readLine());
board=new char[N][N];
for(int i=0;i<N;i++){
board[i]=br.readLine().toCharArray();
}
int result=0;
//가로
for(int i=0;i<N;i++){
int sum=0;
for(int j=0;j<N-1;j++){
if(board[i][j]==board[i][j+1]){
sum++;
}else{
result=Math.max(result,sum);
sum=0;
}
}
result=Math.max(result,sum);
}
//세로
for(int i=0;i<N;i++){
int sum=0;
for(int j=0;j<N-1;j++){
if(board[j][i]==board[j+1][i]){
sum++;
}else{
result=Math.max(result,sum);
sum=0;
}
}
result= Math.max(result,sum);
}
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
for(int k=0;k<4;k++) {
if(i+dir[k][0]<0 || i+dir[k][0]>=N || j+dir[k][1]<0 || j+dir[k][1]>=N) continue;;
if (board[i][j] != board[i+dir[k][0]][j+dir[k][1]]) {
//자리 교환 후 최대로 먹을 수 있는 사탕 개수 구하기
result=Math.max(result,change(i,j,i+dir[k][0],j+dir[k][1]));
}
}
}
}
System.out.println(result+1);
}
private static int change(int x1, int y1, int x2, int y2) {
int tmp=0;
char[][] copy= new char[N][N];
for(int i=0;i<N;i++){
copy[i]=Arrays.copyOf(board[i],N);
}
char swap=copy[x1][y1];
copy[x1][y1]=copy[x2][y2];
copy[x2][y2]=swap;
//가로
for(int i=0;i<N;i++){
int sum=0;
for(int j=0;j<N-1;j++){
if(copy[i][j]==copy[i][j+1]){
sum++;
}else{
tmp=Math.max(tmp,sum);
sum=0;
}
}
tmp=Math.max(tmp,sum);
}
//세로
for(int i=0;i<N;i++){
int sum=0;
for(int j=0;j<N-1;j++){
if(copy[j][i]==copy[j+1][i]){
sum++;
}else{
tmp=Math.max(tmp,sum);
sum=0;
}
}
tmp= Math.max(tmp,sum);
}
return tmp;
}
}완전탐색을 통해 사탕의 종류가 다르면 교환해주고 가로, 세로 방향으로 봤을 때 같은 사탕의 개수가 가장 긴 경우를 모두 찾아주면 된다.
인접한 모든 문자들을 비교해야하기 때문에 상하좌우에 있는 문자들을 모두 확인한다. 문자가 다르다면 위치를 바꿔주고 가로와 세로 기준으로 같은 문자가 가장 길게 연속한 경우를 찾아준다.
이때, 다음 문자와 같은 값이 같을땐 변수값을 ++ 해주지만
다른 값일때 처리해야하는 일이 있다.
예를 들어 한 줄에 CPPPPPPPCYPPPYYYY 와 같은 경우가 있다고 생각해보자.
처음의 P의 연속한 길이가 가장 긴데, C를 만나면 다음 PPP를 만날 때 이 길이를 0부터 다시 카운트를 해주어야한다.
이것을 고려하면 다른 문자를 만났을 경우에 Math.max()를 통해 현재의 답과 비교하여 큰 값을 저장해주고 sum변수를 0으로 초기화 해준다.
반복하면 같은 문자가 연속해서 반복되는 가장 긴 경우의 길이를 구할 수 있다.!
