[백준 알고리즘] 3085번: 사탕게임
March 02, 2021
https://www.acmicpc.net/problem/3085
문제
문제
상근이는 어렸을 적에 “봄보니 (Bomboni)” 게임을 즐겨했다.
가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.
사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 보드의 크기 N이 주어진다. (3 ≤ N ≤ 50)
다음 N개 줄에는 보드에 채워져 있는 사탕의 색상이 주어진다. 빨간색은 C, 파란색은 P, 초록색은 Z, 노란색은 Y로 주어진다.
사탕의 색이 다른 인접한 두 칸이 존재하는 입력만 주어진다.
출력
첫째 줄에 상근이가 먹을 수 있는 사탕의 최대 개수를 출력한다.
풀이
브루트포스 문제이므로 모든 두 위치를 바꾸어보고 각 행과 열에 연속된 글자가 얼마나 있는지 확인해보면 된다. 처음에는 4방향에 대해 모두 바꾸어보는 방식으로 구현했는데, 이렇게 하기보다는 어차피 두 위치를 바꾸고 제자리로 돌려두면 똑같은 교환이 이후에 한번 더 일어나기 때문에 무조건 왼쪽으로 바꾸는 경우와 아래로 바꾸는 경우만 신경쓰면 더 효율적으로 해결할 수 있었다.
코드
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
vector<string> board;
int n;
int countCandy(){
int n = (int)board.size();
int answer = 1;
for(int i = 0 ; i < n ; i++){
int count = 1; // 연속된 개수를 저장
for (int j = 1 ; j < n ; j++){
if (board[i][j] == board[i][j-1]){
count += 1;
}
else{
count = 1;
}
answer = max(answer, count);
}
count = 1;
for (int j = 1 ; j < n ; j++){
if (board[j][i] == board[j-1][i]){
count++;
}
else{
count = 1;
}
answer = max(answer, count);
}
}
return answer;
}
int main (){
int answer = 0;
cin >> n;
for (int i = 0 ; i < n ; i++){
string line;
cin >> line;
board.push_back(line);
}
for (int i = 0 ; i < n ; i++){
for(int j = 0 ; j < n ; j++){
if(j + 1 < n){ // 오른쪽과 교환
swap(board[i][j], board[i][j+1]);
answer = max(answer, countCandy());
swap(board[i][j], board[i][j+1]);
}
if(i + 1 < n){ // 아래와 교환
swap(board[i][j], board[i+1][j]);
answer = max(answer, countCandy());
swap(board[i][j], board[i+1][j]);
}
}
}
printf("%d", answer);
}
