백준 3085 C++

백준 3085

문제

상근이는 어렸을 적에 “봄보니 (Bomboni)” 게임을 즐겨했다.

가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.

사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 보드의 크기 N이 주어진다. (3 ≤ N ≤ 50)

다음 N개 줄에는 보드에 채워져 있는 사탕의 색상이 주어진다. 빨간색은 C, 파란색은 P, 초록색은 Z, 노란색은 Y로 주어진다.

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

출력

N이 최대 50이니 O(N^2)해도 2500이다. 그냥 브루트포스를 해도 된다.

처음에는 문제를 읽었을 때, 잘못 읽어서 그 사탕을 여러 번 돌려서 최대의 길이를 구하는 문제로 인식해서, 갯수를 읽어서, 최대한 길게 만드는건가 했는데, 한 번만 돌리는 거였다…

#include <iostream>
#include <algorithm>
#include <vector>

#include <queue>

using namespace std;


char map[51][51];
bool visited[51][51][4];

int N;

int dy[4] = { 0,0,1,-1 };
int dx[4] = { 1,-1, 0, 0 };


int result = -1;

int cal() {

	int res = -1;

	for (int y = 0; y < N; ++y) {
		int tmp = 1;
		for (int x = 1; x < N; ++x) {
			if (map[y][x - 1] == map[y][x]) tmp++;
			else {
				res = max(res, tmp);
				tmp = 1;
			}
			res = max(tmp, res);
		}
	}

	for (int y = 0; y < N; ++y) {
		int tmp = 1;
		for (int x = 1; x < N; ++x) {
			if (map[x][y] == map[x - 1][y]) tmp++;
			else {
				res = max(res, tmp);
				tmp = 1;
			}
			res = max(tmp, res);
		}
	}
	return res;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> N;

	for (int y = 0; y < N; ++y) {
		for (int x = 0; x < N; ++x) {
			cin >> map[y][x];
		}
	}
	
	for (int y = 0; y < N; ++y) {
		for (int x = 1; x < N; ++x) {
			swap(map[y][x - 1], map[y][x]);
			result = max(result, cal());
			swap(map[y][x - 1], map[y][x]);

			swap(map[x][y], map[x - 1][y]);
			result = max(result, cal());
			swap(map[x][y], map[x - 1][y]);
		}
	}

	cout << result;
	return 0;
}

BOJ 카테고리 내 다른 글 보러가기