백준 - [BOJ 3085] 사탕게임

백준 온라인 져지(BOJ)에서 제공 되는 3085번 문제는 브루트 포스(Brute-Froce, 완전 탐색) 유형이다.

해당 문제는 code.plus 기초 2/2, 브루트포스에 게시된 문제이다.

---

문제

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

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

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

입력

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

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

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

출력

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

---

풀이

접근법 (사탕 교환)

 

1. 인접한 칸끼리 교환

2. 먹을 수 있는 최대의 사탕을 찾음.

3. 매 칸 반복 ( 다음 인접한 칸 끼리의 교환을 위해 1을 한번 더 수행 )

각 Index에 인접한 칸은 상하좌우로 4개씩 있음. 

매 칸 상하좌우의 index와 사탕을 교환한다면?

모든 칸은 N^2개 존재하므로 N^2개 마다 4번씩 교환한다.

시간 : O(4N^2), N <= 50 이므로 시간이 매우 충분하다고 생각한다.

---

개선된 풀이

(0, 0) 일 때, 인접한 칸 중 윗쪽과 왼쪽을 생각해보자. out of bounds이다. 
또, 배열의 탐색 이중 for문을 생각해보자. 

한 행에 속한 모든 열의 원소를 다 방문한 뒤 다음 행을 탐색하게 된다.

즉, 한 원소 입장에서 왼쪽과 윗쪽에 속한 원소들은 이미 이전 단계에서 한 번의 교환이 발생했다는 것이다.

그러므로 인접한 네 방향 중 두 방향만 탐색하면 된다는 장점이 있다.

시간은 O(4N^2) -> O(2N^2)으로 줄어든다.

---

핵심 로직 (사탕 교환 후 가장 많이 먹을 수 있는 개수 찾기)

 

해당 문제는 n*n 이므로 이건 매우 간단하다.

for(int i = 0; i<n; i++) {
    for(int j = 0; j<n; j++) {
    	arr[i][j] = 0; // col
    }
    for(int j = 0; j<n; j++) {
    	arr[j][i] = 0; // row
    }
}

주황색 숫자 = row, 검정색 숫자 = col

 

1. 한 행 또는 열에 대해서 사탕의 개수를 센다.

2. 현재 색깔과 다른 사탕을 발견한다면 다시 1개로 줄인다.

3. 1번에 대해서 가장 큰 값을 저장해둔다.

 

위와같은 방법도 개선할 수 있다.

위 그림처럼 스왑한다고 가정

col 에서 swap이 발생할 시 해당 (col, col+1, row) 만 바뀐 것이므로 3가지만 탐색하면 된다.

row 에서 swap이 발생할 시 해당 (row, row+1, col) 만 바뀐 것이다.

 

즉, N x N에 대해서 확인할 필요 없이 특정 두 열과 한 행 또는 한 열과 두 행만 탐색하면 된다.

물론 완전탐색으로 풀이가 될 만큼 N의 개수가 적어서 굳이 효율을 따질 필요는 없다.

 

개선된 방법의 주의할 점이 있다.

변경된 위치에서만 탐색을 진행하므로 변경되지 않는 초기에 탐색을 진행하는 경우가 필요하다.

맨처음 한 번, 전체에서 사탕의 개수를 찾으면 된다. 

 

Brute-Force

/*
	authored by jihwankim
	dev-dot.tistory.com
	code.plus
*/
#include <iostream>
#include <algorithm>

using namespace std;

int n;

int readCnt(vector<string> &arr, int y, int ye, int x, int xe) {
	char c;
	int cnt;
	int maxCnt = 0;
	
	//readCol
	for(int i = y; i<=ye; i++) {
		c = arr[i][0]; cnt = 0;
		for(int j = 0; j<n; j++) {
			if(arr[i][j] != c) {
				maxCnt = max(maxCnt, cnt);
				c = arr[i][j];
				cnt = 0;
			}
			if(arr[i][j] == c) cnt++;
		}
		maxCnt = max(maxCnt, cnt);
		
	}
	//readRow
	for(int i = x; i<=xe; i++) {
		c = arr[0][i]; cnt = 0;
		for(int j = 0; j<n; j++) {
			if(arr[j][i] != c) {
				maxCnt = max(maxCnt, cnt);
				c = arr[j][i];
				cnt = 0;
			}
			if(arr[j][i] == c) cnt++;
		}
		maxCnt = max(maxCnt, cnt);
		
	}
		
	return maxCnt;
}

int initRead(vector<string> &arr) {
	char c; int cnt;
	int maxCnt = 0;
	
	for(int i = 0; i<n; i++) {
		//readCol
		c = arr[i][0]; cnt = 0;
		for(int j = 0; j<n; j++) {
			if(arr[i][j] != c) {
				maxCnt = max(maxCnt, cnt);
				c = arr[i][j];
				cnt = 0;
			}
			if(arr[i][j] == c) cnt++;
		}
		maxCnt = max(maxCnt, cnt);
		c = arr[i][0]; cnt = 0;
		
		//readRow
		for(int j = 0; j<n; j++) {
			if(arr[j][i] != c) {
				maxCnt = max(maxCnt, cnt);
				c = arr[j][i];
				cnt = 0;
			}
			if(arr[j][i] == c) cnt++;
		}
		maxCnt = max(maxCnt, cnt);
	}
	return maxCnt;
}

int solve(vector<string> &arr) {
	int maxCnt = initRead(arr);
	for(int i = 0; i<n; i++) {
		for(int j = 0; j<n; j++) {
			if(i+1 < n) {
				if(arr[i][j] != arr[i+1][j]) {
					swap(arr[i][j], arr[i+1][j]);
					maxCnt = max(maxCnt, readCnt(arr, i, i+1, j, j));
					swap(arr[i][j], arr[i+1][j]);
				}
			}
			
			if(j+1 < n) {
				if(arr[i][j] != arr[i][j+1]) {
					swap(arr[i][j], arr[i][j+1]);
					maxCnt = max(maxCnt, readCnt(arr, i, i, j, j+1));
					swap(arr[i][j], arr[i][j+1]);
				}
			}
		}
	}
	return maxCnt;
}

vector<string> input() {
	cin >> n;
	vector<string> s(n);
	for(int i = 0; i<n; i++) {
		cin >> s[i];
	}
	return s;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	
	vector<string> s = input();
	cout << solve(s);
	
	return 0;
}

 

해당 문제는 예전에 블로그를 시작하기 전, 단 한 번 노션에 작성해두었던 내용인데..

지금와서 보니까 수정할 점이 너무 많다..

그래도 성장한 것 같아서 기쁘다 ^^

코드도 훨씬 간략하게 줄일 수 있겠고 로직도 더 간편한 방법이 떠오른다.

 

참고할 포스트

 

아직 미작성

문제

 

https://www.acmicpc.net/problem/3085

3085번: 사탕 게임

https://code.plus/course/42

알고리즘 기초 2/2