백준 12100 삼성기출 2480(Easy)

 

알고리즘 자체의 난이도는 높지 않지만 예외케이스와, 기저가 많아 집중하고 체계적으로 코딩해야되는 문제였습니다.

 

BFS,DFS 모두 사용가능하나 brute force로 흝어봐야하는 문제이기 때문에 어차피 시간복잡도가 같다면,

메모리를 더 아낄 수 있고 코드도 좀 더 깔끔한 재귀함수 DFS를 추천드립니다.

 

(재귀함수를 사용하면 function stack을 계속 만드는 오버헤드는 있다고 합니다.

다만 함수 내용이 짧을 수록 함수 stack 생성 오버헤드가 상대적으로 더 큰 것이지, 그외는 괜찮은 듯합니다.

DFS도 stack 자료구조를 사용하면 재귀를 사용하지 않을 수 있습니다.)

#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
 
typedef unsigned long long ull;
typedef vector<vector<ull>> vvi;
 
vvi Map;
int N;
ull Max_block;
 
//움직임에 대한 결과 클래스
struct Res {
	vvi Map; 
	ull mB; //Max_Block
	int cnt; //블록의 개수
	Res(vvi m, ull b, int c) :Map(m), mB(b), cnt(c) {}
};
 
// class_dir은 상하좌우 flag
// class_dir에 따라 for문 속에서 switch,if문이 계속 돌아가는 것은
// 함수가 콜된 후로 class_dir은 바뀌지 않으므로 분기예측으로 성능이 개선될 수 있다.
Res mov(vvi M,int class_dir) {
	int src;
	int dst;
	int dir;
	int cnt = 0;
	ull c_m_block=0;
 
	//우, 상 방향움직임
	if (class_dir == 0 || class_dir == 2)
	{
		src = 0;
		dst = N;
		dir = 1;
	}
	// 좌, 하 방향
	else
	{
		src = N-1;
		dst = -1;
		dir = -1;
	}
	
	bool flag = false; //한번 합쳐진 블록이라는 flag.
 
	// class_dir에 따라 한 라인씩 순회
	for (int i = 0; i < N; i++)
	{
		vector<ull> line;
		for (int j = src; j != dst; j+=dir)
		{
			int tmp; 
 
			if (class_dir < 2) tmp = M[i][j];
			else tmp = M[j][i];
 
			//앞에 값과 같고, 앞에 값이 flag=flase라면 합한다.
		    if (tmp != 0 && !line.empty() && !flag && line.back() == tmp)
			{
				line[line.size() - 1] += tmp;
				flag = true;
			}
			//해당사항 없고 빈칸이 아니라면, line에 추가.
			else if (tmp != 0)
			{
				line.push_back(tmp);
				flag = false;
			}
		}
 
		//맵에 남아있는 숫자를 카운트한다.
		cnt += line.size();
		
		// 결과로 나온 line값을 
		// class_dir에 맞춰서 Map에 다시 써준다.
		// 이때 가장 큰 block값을 저장한다.
		for (int k = 0; k < line.size(); k++)
		{
			switch (class_dir)
			{
			case 0: 
				M[i][k] = line[k];
				break;
			case 1: 
				M[i][N - 1 - k] = line[k];
				break;
			case 2: 
				M[k][i] = line[k];
				break;
			case 3 : 
				M[N - 1 - k][i] = line[k];
				break;
			}
 
			c_m_block = max(c_m_block, line[k]);
		}
		//나머지 뒤에는 0 삽입
		for (int k = line.size(); k < N; k++)
			switch (class_dir)
			{
			case 0:
				M[i][k] = 0;
				break;
			case 1:
				M[i][N - 1 - k] = 0;
				break;
			case 2:
				M[k][i] =0;
				break;
			case 3:
				M[N - 1 - k][i] = 0;
				break;
			}
 
	}
	//변경된 Map, 가장큰 블록 값, 남아있는 블록의 수 
	return Res(M,c_m_block,cnt);
}
 
void brute(vvi M, int deep, ull c_m_b, int c_cnt)
{
	Max_block = max(Max_block, c_m_b);
 
	if (c_cnt == 1) return; //블록이 1개밖에 안남으면 더 진행할 필요없다.
	if (deep >= 5) return;
	if (Max_block >= pow(c_m_b, 6 - deep)) return; //프로미싱 하지 않다면, 더이상 진행할 필요 없다.
 
	for (int i = 0; i < 4; i++)
	{
		Res res = mov(M, i);
		//한번에 움직임으로 나온 결과값을 다음 brute로 전달.
		brute(res.Map, deep + 1, res.mB, res.cnt);
	}
}
 
// 디버깅용 맵 확인!
void show(vvi tmp) 
{
	cout << endl;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++)
			cout << tmp[i][j]<<" ";
		cout << endl;
	}
	cout << endl;
}
 
int main() {
	cin >> N;
 
	Map = vvi(N, vector<ull>(N));
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++) 
			cin >> Map[i][j];
 
	//최소개수는 1개일 수도있지만,
	//2로 시작해도, brute에서 금방 1을 인식하고 반환한다.
	brute(Map, 0, 2, 2);
	cout << Max_block;
} 

 

최대한 비슷하게 동작하는 case에 대해서는 코드를 재사용하려고 노력했습니다.

 

조금 더 코드를 최적화 시킨다면 2차원 vector를 1차원 vector로 평탄화 한다면,

2차원 vector에서 V[행][열] 순서로 정해져서 행이동과 열이동에 같은 코드를 쓸수 없던 점을

row,col 역할을 하는 변수를 사용하여 코드의 범용성을 넓힐 수 있습니다.

 

 

예로 N = 4,  i = (1 ~ N-1) 이라면 Map[ start + Jump*i ]을 통해서 원하는 2차원 맵의 start지점에서

case에 따라 Jump값만 배정을 다르게 한다면, 같은 코드로도 다른 동작을 수행시킬 수 있습니다.

Jump = 4 라면 한 행씩 하로 이동 Jump = 1이라면 한 열씩 우로 이동,

Jump = -4 라면 상, Jump = -1이라면 좌로 이동합니다.

 

(

사실 C의 기본 2차원( ex)int arr[5][5] ) 배열은 메모리에 포인터로 접근할때는 위 방식처럼 이미 배정되어 있으나,

DFS에 사용하려면 배열의 복사 생성과, 함수가 끝날때 메모리를 해제 기능을 직접 구현해야됩니다.

 

그러므로, 이미 깊은복사생성자와 소멸자가 다 구현되어있는 STL의 vector 사용이 용이 합니다.

)

 

하지만 한 가지의 코드가 여러 케이스에서도 잘 동작하도록 예외를 고려하는 것은 쉬운일도 아니고,

코드의 의미를 파악하기도 어려우며, 실수가 생기기 쉽습니다. 

 

생각한 알고리즘 아이디어가 명확하다면, 코드가 길어지더라도 예외케이스가 입력에 따라 커지는게 아닌 이상

몇줄 더 길게 코딩하는게 실수를 줄이고 명확할 수 있겠습니다.