상하좌우 기울이기 문제 회전하여 한 방향만 구현하기 (회전, 기울이기)

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

12100번: 2048 (Easy)

참고 ) https://na982.tistory.com/83

[삼성 SW 역량 테스트] 2048(Easy)

 

기존에는 아래 링크와 같이 상하좌우를 따로 구별하여 구현하였다.

하지만, 위 강의를 듣고 상하좌우를 따로 구현하는 것보다 회전을 시키는 것이 더 실수가 적을 수 있다는 것을 알게 되었다.

https://minjheyy.tistory.com/34

#include <iostream>
#include <algorithm>
using namespace std;

/*
한가지 방향만 구현할수 있다.
*/

int n, ret;
struct BOARD {
	int map[20][20];

	void rotate () {
		int temp[20][20];

		// rotate 90 degree clock wise
		// x, y 를 바꿔주고 법위를 바꿔주면 됩니다.
		for(int y=0; y<n; y++)
			for(int x=0; x<n; x++)
				temp[y][x] = map[n-x-1][y];

		// copy
		for(int y=0; y<n; y++)
			for(int x=0; x<n; x++)
				map[y][x] = temp[y][x];
	}

	int get_max() {
		int ret = 0;
		for(int y=0; y<n; y++)
			for(int x=0; x<n; x++)
				ret = max(ret, map[y][x]);

		return ret;
	}

	void up() {
		int temp[20][20] = {0,};

		for(int x=0; x<n; x++) {
			int flag = 0; 
			int target = -1;
			for(int y=0; y<n; y++) {
				if(map[y][x] == 0) continue;

				if(flag == 1 && map[y][x] == temp[target][x]) {
					temp[target][x] *= 2;
					flag = 0;
				}
				else {
					temp[++target][x] = map[y][x];
					flag = 1;
				}
			}
		}
		for(int y = 0; y<n; y++)
			for(int x = 0; x<n; x++)
				map[y][x] = temp[y][x];
	}
};

void dfs(BOARD cur, int count) {
	if(count == 5) {
		ret = max(ret, cur.get_max());
		return;
	}
	for(int dir = 0; dir <4; dir++) {
		BOARD next = cur;
		next.up();
		dfs(next, count+1);
		cur.rotate();
	}

} 

int main() {
	BOARD board;
	scanf("%d", &n);

	for(int y=0; y<n; y++)
		for(int x=0; x<n; x++)
			scanf("%d", &board.map[y][x]);
		
	dfs(board, 0);
	printf("%d\n", ret);

	return 0;
}

구조체 내부에 함수들을 정의하여 사용가능하다.

 

시계방향 90 도 회전

void rotate () {
    int temp[20][20];

    // rotate 90 degree clock wise
    // x, y 를 바꿔주고 법위를 바꿔주면 됩니다.
    for(int y=0; y<n; y++)
    	for(int x=0; x<n; x++)
    		temp[y][x] = map[n-x-1][y];

    // copy
    for(int y=0; y<n; y++)
    	for(int x=0; x<n; x++)
    		map[y][x] = temp[y][x];
}

반시계방향 90도 회전

void rotate () {
		int temp[20][20];
       
		// x, y 를 바꿔주고 법위를 바꿔주면 됩니다.
		for(int y=0; y<n; y++)
			for(int x=0; x<n; x++)
				temp[y][x] = map[x][n-y-1];

		// copy
		for(int y=0; y<n; y++)
			for(int x=0; x<n; x++)
				map[y][x] = temp[y][x];
	}