관리 메뉴

KoreanFoodie's Study

SW 역량테스트 - [백준] 2048 문제 풀이/해답/코드 (C++ / JAVA) 본문

Data Structures, Algorithm/SW 역량테스트

SW 역량테스트 - [백준] 2048 문제 풀이/해답/코드 (C++ / JAVA)

hashnut 2020. 10. 15. 23:30

 


SW 역량 테스트 준비를 위한 핵심 문제들을 다룹니다!

해답을 보기 전에 문제를 풀어보시거나, 설계를 하고 오시는 것을 추천드립니다. 

코드에 대한 설명은 주석을 참고해 주세요 :)

 


문제 링크 : www.acmicpc.net/problem/12100

해답 코드 : 

 

#include <iostream>
#include <vector>

using namespace std;

int N;
int ans;
int map[20][20];

// Up, Down, Left, Right
int dR[4] = {-1, 1, 0, 0};
int dC[4] = {0, 0, -1, 1};

void copy_map(int dst[20][20], int src[20][20]) {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			dst[i][j] = src[i][j];
		}
	}
}

int max_map() {
	int max_num = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (max_num < map[i][j]) {
				max_num = map[i][j];
			}
		}
	}
	return max_num;
}

void up() {
	// store numbers to be located, for each line
	vector<int> line;

	int cur;

	for (int col = 0; col < N; col++) {
		
		cur = -1;

		for (int row = 0; row < N; row++) {

			if (map[row][col] == 0) {
				continue;
			} else if (map[row][col] == cur) {
				line.pop_back();
				line.push_back(cur * 2);
				cur = -1;
			}
			else {
				cur = map[row][col];
				line.push_back(cur);
			}

		}

		for (int i = 0; i < N; i++) {
			if (i < line.size()) {
				map[i][col] = line[i];
			}
			else {
				map[i][col] = 0;
			}
		}
		line.clear();
	}

}

void down() {
	// store numbers to be located, for each line
	vector<int> line;

	int cur;

	for (int col = 0; col < N; col++) {

		cur = -1;

		for (int row = N-1; row >= 0; row--) {

			if (map[row][col] == 0) {
				continue;
			} else if (map[row][col] == cur) {
				line.pop_back();
				line.push_back(cur * 2);
				cur = -1;
			}
			else {
				cur = map[row][col];
				line.push_back(cur);
			}

		}

		for (int i = 0; i < N; i++) {
			if (i < line.size()) {
				map[N - 1 - i][col] = line[i];
			}
			else {
				map[N - 1 - i][col] = 0;
			}
		}
		line.clear();

	}

}


void left() {
	// store numbers to be located, for each line
	vector<int> line;

	int cur;

	for (int row = 0; row < N; row++) {

		cur = -1;

		for (int col = 0; col < N; col++) {

			if (map[row][col] == 0) {
				continue;
			}
			else if (map[row][col] == cur) {
				line.pop_back();
				line.push_back(cur * 2);
				cur = -1;
			}
			else {
				cur = map[row][col];
				line.push_back(cur);
			}

		}

		for (int i = 0; i < N; i++) {
			if (i < line.size()) {
				map[row][i] = line[i];
			}
			else {
				map[row][i] = 0;
			}
		}
		line.clear();
	}

}

void right() {
	// store numbers to be located, for each line
	vector<int> line;

	int cur;

	for (int row = 0; row < N; row++) {

		cur = -1;

		for (int col = N - 1; col >= 0; col--) {

			if (map[row][col] == 0) {
				continue;
			}
			else if (map[row][col] == cur) {
				line.pop_back();
				line.push_back(cur * 2);
				cur = -1;
			}
			else {
				cur = map[row][col];
				line.push_back(cur);
			}

		}


		for (int i = 0; i < N; i++) {
			if (i < line.size()) {
				map[row][N - 1 - i] = line[i];
			}
			else {
				map[row][N - 1 - i] = 0;
			}
		}
		line.clear();
	}

}

void dfs(int cnt) {

	// terminator
	if (cnt > 5) {
		ans = max_map() > ans ? max_map() : ans;
		return;
	}

	int backup[20][20];
	copy_map(backup, map);
	

	for (int dir = 0; dir < 4; dir++) {

		if (dir == 0) {
			up();
		}
		else if (dir == 1) {
			down();
		}
		else if (dir == 2) {
			left();
		}
		else {
			right();
		}

		dfs(cnt + 1);
		
		copy_map(map, backup);
	}

}


int main() {

	cin >> N;
	ans = 0;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> map[i][j];
		}
	}

	dfs(1);

	cout << ans;

}

 

SW 역량테스트 준비 - [모의 SW 역량테스트] 풀이 / 코드 / 답안 (C++ / JAVA)

SW 역량테스트 준비 - C++ 코드, Java 코드

SW 역량테스트 준비 - 백준 알고리즘 문제

0 Comments
댓글쓰기 폼