글 읽기 - 2048 게임 12100번 질문입니다...SW역량 Test 기출

lawliet777 4년 전 1

정말 어렵게 어렵게 취업을 위해 공부중인데

하루종일 고민해서 짠 코드가 틀려버리니...멘탈이 나가네요...

각설하고,

다른분의 풀이를 보니까 회전하여서 상 하 좌 우를 한번에 처리하였던데..

저는 아직 걸음마 수준이라 다음과 같이 4개의 함수를 각각 작성하고, switch case문으로 dfs를 돌렸네요.

아래 코드에서 정답과 다르게 나오는 부분을 좀 여쭤봐도 될까요?

제가 디버깅한 바로는 제대로 나오는것 같은데...ㅠㅠ 부탁드립니다.

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

#define MIN(a,b) a>b ? b:a;
#define MAX(a,b) a<b ? b:a;
const int oo = 0x3f3f3f3f;


//문제 : NxN크기의 보드에서, 블록 상태가 주어졌을 때(상황)
//		 최대 5번까지 이동시켜서 만들 수 있는 가장 큰 블록의 값을 구하시오.
//동치 : 최대 5번까지 이동시킬 때, 나올 수 있는 모든 경우의 수를 구해서
//		 그 중에 제일 큰 블록의 값을 find하기.
//따라서 가능한 모든 경우를 구하되, 조건을 지켜가며 bfs하기. 흠? 이것도 결국 조건인데?
//조건 : 상 하 좌 우로 밀때, 밀리는 곳부터 우선 처리되어야 하며, 한번만 밀려야 함.(즉, 한번 밀린건지, 아닌건지 판별 필요함)
int N;
int board[21][21];
int backup_board[21][21];

int ans=-oo;


int find_max() {
	int ret = -oo;
	for (int x = 1; x <= N;x++) {
		for (int y = 1; y <= N; y++) {
			ret = MAX(ret, board[x][y]);
		}
	}
	return ret;
}

//조건 해석하기
void up() {
	int temp[21][21] = { 0, };
	int canjoin[21][21] = { 0, };//yes가 0 no가 1

	for (int y = 1; y <= N;y++) {
		int t_idxx = 0;//들어온 원소 수라고 생각 최초는 empthy

		for (int x = 1; x <= N;x++) {

			if (board[x][y] == 0) continue;

			//board[x][y]에 뭔가 있을때..
			if (t_idxx == 0) {//처음껀 그냥 옮겨주고
				t_idxx++;
				temp[t_idxx][y] = board[x][y];
			}
			else {//나머지의 경우는 같은거 있는지 검사
				if (temp[t_idxx][y] == board[x][y] && canjoin[t_idxx][y] == 0) {
					temp[t_idxx][y] = temp[t_idxx][y] * 2;
					//t_idxx는 그대로 유지
					canjoin[t_idxx][y] = 1;
				}
				else {
					t_idxx++;
					temp[t_idxx][y] = board[x][y];
				}
			}
		}
	}

	//마지막으로 복사해주고 끝
	for (int x = 1;x <= N;x++) {
		for (int y = 1; y <= N; y++) {
			board[x][y] = temp[x][y];
		}
	}
}

void down() {
	int temp[21][21] = { 0, };
	int canjoin[21][21] = { 0, };//yes가 0 no가 1

	for (int y = 1; y <= N;y++) {
		int t_idxx = 0;//들어온 원소 수라고 생각 최초는 empthy

		for (int x = 1; x <= N;x++) {

			if (board[x][y] == 0) continue;

			//board[x][y]에 뭔가 있을때..
			if (t_idxx == 0) {//처음껀 그냥 옮겨주고
				t_idxx++;
				temp[N + 1 - t_idxx][y] = board[x][y];
			}
			else {//나머지의 경우는 같은거 있는지 검사
				if (temp[N + 1 - t_idxx][y] == board[x][y] && canjoin[N + 1 - t_idxx][y] == 0) {
					temp[N + 1 - t_idxx][y] = temp[N + 1 - t_idxx][y] * 2;
					//t_idxx는 그대로 유지
					canjoin[N + 1 - t_idxx][y] = 1;
				}
				else {
					t_idxx++;
					temp[N + 1 - t_idxx][y] = board[x][y];
				}
			}
		}
	}

	//마지막으로 복사해주고 끝
	for (int x = 1;x <= N;x++) {
		for (int y = 1; y <= N; y++) {
			board[x][y] = temp[x][y];
		}
	}
}


void left() {
	int temp[21][21] = { 0, };
	int canjoin[21][21] = { 0, };//yes가 0 no가 1

	
	for (int x = 1; x <= N;x++) {
		int t_idxx = 0;//들어온 원소 수라고 생각 최초는 empthy

		for (int y = 1; y <= N;y++) {

			if (board[x][y] == 0) continue;

			//board[x][y]에 뭔가 있을때..
			if (t_idxx == 0) {//처음껀 그냥 옮겨주고
				t_idxx++;
				temp[x][N + 1 - t_idxx] = board[x][y];
			}
			else {//나머지의 경우는 같은거 있는지 검사
				if (temp[x][N + 1 - t_idxx] == board[x][y] && canjoin[x][N + 1 - t_idxx] == 0) {
					temp[x][N + 1 - t_idxx] = temp[x][N + 1 - t_idxx] * 2;
					//t_idxx는 그대로 유지
					canjoin[x][N + 1 - t_idxx] = 1;
				}
				else {
					t_idxx++;
					temp[x][N + 1 - t_idxx] = board[x][y];
				}
			}
		}
	}

	//마지막으로 복사해주고 끝
	for (int x = 1;x <= N;x++) {
		for (int y = 1; y <= N; y++) {
			board[x][y] = temp[x][y];
		}
	}
}

void right() {
	int temp[21][21] = { 0, };
	int canjoin[21][21] = { 0, };//yes가 0 no가 1

	for (int x = 1; x <= N;x++) {
		int t_idxx = 0;//들어온 원소 수라고 생각 최초는 empthy

		for (int y = 1; y <= N;y++) {

			if (board[x][y] == 0) continue;

			//board[x][y]에 뭔가 있을때..
			if (t_idxx == 0) {//처음껀 그냥 옮겨주고
				t_idxx++;
				temp[x][t_idxx] = board[x][y];
			}
			else {//나머지의 경우는 같은거 있는지 검사
				if (temp[x][t_idxx] == board[x][y] && canjoin[x][t_idxx] == 0) {
					temp[x][t_idxx] = temp[x][t_idxx] * 2;
					//t_idxx는 그대로 유지
					canjoin[x][t_idxx] = 1;
				}
				else {
					t_idxx++;
					temp[x][t_idxx] = board[x][y];
				}
			}
		}
	}

	//마지막으로 복사해주고 끝
	for (int x = 1;x <= N;x++) {
		for (int y = 1; y <= N; y++) {
			board[x][y] = temp[x][y];
		}
	}
}


//동치 분석으로 인한 bfs코드
void dfs(int count) {
	if (count == 5) {//재귀의 탈출조건(중요)
		int candi = find_max();
		ans = MAX(ans, candi);

        //다시 원상태로 복구해주기
        for(int x=1;x<=N;x++){
            for(int y=1; y<=N;y++)
                board[x][y]=backup_board[x][y];
        }
//		memcpy(board, backup_board, sizeof(backup_board));
		return;
	}


	for (int i = 1;i <= 4;i++) {//1=상, 2=하, 3=좌, 4=우
		switch (i)
		{
		case 1:
			up();
			break;
		case 2:
			down();
			break;
		case 3:
			left();
			break;
		case 4:
			right();
			break;
		default:
			break;
		}
		dfs(count + 1);
	}
}





int main() {
	cin >> N;
	for (int x = 1; x <= N;x++) {
		for (int y = 1; y <= N;y++) {
			cin >> board[x][y];
			backup_board[x][y] = board[x][y];
		}
	}

	int count = 0;
	dfs(count);

	cout << ans;
}

seico75 4년 전 1

이 문제와 같이 복잡한 연산 끝에 단순한 결과가 나오는 경우는 중간 결과들이 정상적인지 확인을 해보셔야 합니다.

답이 간단해서 몇몇 예제의 답은 맞아도 중간 결과는 엉뚱할 수 있습니다. (즉, 계산이 엉뚱하게 되고 있을 수도..)

dfs로 up/down/left/right 를 다 써치를 하는데... 이 경우는 자식이 4개씩 있는 트리를 순회하는 것이라는 아시죠?

즉, up/up/up/up/up 하고 나서 하나 위로 올라가서 down 을 수행하니까 up/up/up/up/down 을 계산하는 것인데...

195 라인에서는 제일 처음으로 돌리네요. 그러면 up/up/up/up/down 이 아니라 down 이 되는거죠.

중간 결과를 체크하기 위한 코드를 짜고 몇가지 경우를 돌렸습니다.

main 함수 수정(테스트를 위한) 및 함수 두개 추가하고 아래 입력을 넣으면 예상 외의 결과를 보여주네요.

void print_board( void)
{
	for (int x = 1; x <= N; x++) 
	{
		for (int y = 1; y <= N; y++) 
		{
			cout << board[x][y] << ' ';
		}
		cout << '\n';
	}
}

void reset( void)
{
	for (int x = 1; x <= N; x++) 
	{
		for (int y = 1; y <= N; y++) 
		{
			board[x][y] = backup_board[x][y];
		}
	}
}


int main() {
	cin >> N;
	for (int x = 1; x <= N;x++) {
		for (int y = 1; y <= N;y++) {
			cin >> board[x][y];
			backup_board[x][y] = board[x][y];
		}
	}

	down();
	down();
	print_board();
	
	reset();
	cout << '\n';
	
	left();
	print_board();

	return 0;
}

lawliet777 4년 전 0

댓글 너무 감사합니다..!!

이전 정보를 저장해서 backtrack한다는게 쉽지 않네요...

저렇게 단순한게 아니라, 메모해야할 것이 더 많은거 같은데..

매번 dfs를 실행하기 전에 backup_board로 board의 내용을 옮겨주는것이 비효율적인것 같기도 하구요ㅠㅠ

다른 방식으로 코드를 구현하는게 일반적일까요?(메모를 하는것이 아닌..?어떤..?)

답변 너무 감사합니다!

lawliet777 4년 전 0

아래처럼 바꿨는데, 백트레킹이 잘 안되네요 ㅠㅠㅠ

void dfs(int count) {
	int backup_board[21][21]={0};
	memcpy(backup_board, board, sizeof(board));

	if (count == 5) {//재귀의 탈출조건(중요)
		int candi = find_max();
		ans = MAX(ans, candi);

		memcpy(board, backup_board, sizeof(backup_board));
		return;
	}


	for (int i = 1;i <= 4;i++) {//1=상, 2=하, 3=좌, 4=우

		switch (i)
		{
		case 1:
			up();
			break;
		case 2:
			down();
			break;
		case 3:
			left();
			break;
		case 4:
			right();
			break;
		default:
			break;
		}
		dfs(count + 1);
		memcpy(board, backup_board, sizeof(backup_board));
	}

}

seico75 4년 전 1

4개 움직이는 함수 중에서 정상 동작하는 것은 up 밖에 없어 보입니다.

seico75 4년 전 1

잘 안되면 링크 참고해보세요. https://ideone.com/kKUJDx

그리고 지금 작성하신 것이 up/down 등의 함수에서 temp 배열을 쓰는데, 배열 백업하는 것과 중복되는 것 같습니다.

이것을 잘 활용하면 백업을 없앨 수 있을 것 같습니다.

이것은 아래 링크... https://ideone.com/9MDG7L

lawliet777 4년 전 0

주말동안 사이트를 못들어 왔는데, 직접 코드를 재작성 해주셔서 참고할 수 있게 도와주시니 감사할 따름이네요...ㅠㅠㅠ감동입니다....

자기 전에 들어와서 말씀듣고 혼자서 먼저 수정해 보았는데, 보니까 말씀데로 down과 right두개가 말썽이네요(위에 처음에 올린 코드는 심지어 left right함수의 동작 네이밍마져 바꿔져 있는...)

어렵다고 느낀 문제를 한문제 풀어나갈 때 마다, 제 코드습관의 나쁜점을 고쳐나가야 겠다는 생각이 또 듭니다.

특히 말씀데로 이렇게 코드를 복붙 형식으로 비슷한 동작을 하는 함수를 다시 짤 때,

더욱 더 주의하고 재 검사가 필요하다는 것도 느꼈고요...

참고해주신 코드처럼 dfs에 배열을 그냥 넘겨버리는 것도 하나의 좋은 방법이 된다는점 배우고 갑니다.

여러모로 답변해 주셔서 정말 감사합니다!! 복받으실 거에요^^

#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include<algorithm>
#include <memory.h>

using namespace std;

typedef long long LL;
typedef long long int LLI;
typedef long L;
#define MIN(a,b) a>b ? b:a;
#define MAX(a,b) a<b ? b:a;

const int oo = 0x3f3f3f3f;


//문제 : NxN크기의 보드에서, 블록 상태가 주어졌을 때(상황)
//		 최대 5번까지 이동시켜서 만들 수 있는 가장 큰 블록의 값을 구하시오.
//동치 : 최대 5번까지 이동시킬 때, 나올 수 있는 모든 경우의 수를 구해서
//		 그 중에 제일 큰 블록의 값을 find하기
//		 (왜냐면, 경우의 수가 해봤자 4^5=1024 -> leaf가 1024고 이 때 nonleaf가 1024보다 작은게 분명함으로 (tree구조), 2*1024*20*20연산)
//따라서 가능한 모든 경우를 구하되, 조건을 지켜가며 bfs하기. 흠? 이것도 결국 조건인데?
//조건 : 상 하 좌 우로 밀때, 밀리는 곳부터 우선 처리되어야 하며, 한번만 밀려야 함.(즉, 한번 밀린건지, 아닌건지 판별 필요함)
int N;
int board[21][21];
//int backup_board[21][21];

int ans = 0;


int find_max() {
	int ret = -oo;
	for (int x = 1; x <= N;x++) {
		for (int y = 1; y <= N; y++) {
			ret = MAX(ret, board[x][y]);
		}
	}
	return ret;
}

//조건 해석하기
void up() {
	int temp[21][21] = { 0, };
	int canjoin[21][21] = { 0, };//yes가 0 no가 1

	for (int y = 1; y <= N;y++) {
		int t_idxx = 0;//들어온 원소 수라고 생각 최초는 empthy
	
		for (int x = 1; x <= N;x++) {

			if (board[x][y] == 0) continue;

			//board[x][y]에 뭔가 있을때..
			if (t_idxx == 0) {//처음껀 그냥 옮겨주고
				t_idxx++;
				temp[t_idxx][y] = board[x][y];
			}
			else {//나머지의 경우는 같은거 있는지 검사
				if (temp[t_idxx][y] == board[x][y] && canjoin[t_idxx][y] == 0) {
					temp[t_idxx][y] = temp[t_idxx][y] * 2;
					//t_idxx는 그대로 유지
					canjoin[t_idxx][y] = 1;
				}
				else {
					t_idxx++;
					temp[t_idxx][y] = board[x][y];
				}
			}
		}
	}

	//마지막으로 복사해주고 끝
	for (int x = 1;x <= N;x++) {
		for (int y = 1; y <= N; y++) {
			board[x][y] = temp[x][y];
		}
	}
}

void down() {
	int temp[21][21] = { 0, };
	int canjoin[21][21] = { 0, };//yes가 0 no가 1

	for (int y = 1; y <= N;y++) {
		int t_idxx = 0;//들어온 원소 수라고 생각 최초는 empthy
	
		for (int x = N; x >= 1; x--) {

			if (board[x][y] == 0) continue;

			//board[x][y]에 뭔가 있을때..
			if (t_idxx == 0) {//처음껀 그냥 옮겨주고
				t_idxx++;
				temp[N + 1 - t_idxx][y] = board[x][y];
			}
			else {//나머지의 경우는 같은거 있는지 검사
				if (temp[N + 1 - t_idxx][y] == board[x][y] && canjoin[N + 1 - t_idxx][y] == 0) {
					temp[N + 1 - t_idxx][y] = temp[N + 1 - t_idxx][y] * 2;
					//t_idxx는 그대로 유지
					canjoin[N + 1 - t_idxx][y] = 1;
				}
				else {
					t_idxx++;
					temp[N + 1 - t_idxx][y] = board[x][y];
				}
			}
		}
	}

	//마지막으로 복사해주고 끝
	for (int x = 1;x <= N;x++) {
		for (int y = 1; y <= N; y++) {
			board[x][y] = temp[x][y];
		}
	}
}


void left() {
	int temp[21][21] = { 0, };
	int canjoin[21][21] = { 0, };//yes가 0 no가 1

	for (int x = 1; x <= N;x++) {
		int t_idxx = 0;//들어온 원소 수라고 생각 최초는 empthy
	
		for (int y = 1; y <= N;y++) {

			if (board[x][y] == 0) continue;

			//board[x][y]에 뭔가 있을때..
			if (t_idxx == 0) {//처음껀 그냥 옮겨주고
				t_idxx++;
				temp[x][t_idxx] = board[x][y];
			}
			else {//나머지의 경우는 같은거 있는지 검사
				if (temp[x][t_idxx] == board[x][y] && canjoin[x][t_idxx] == 0) {
					temp[x][t_idxx] = temp[x][t_idxx] * 2;
					//t_idxx는 그대로 유지
					canjoin[x][t_idxx] = 1;
				}
				else {
					t_idxx++;
					temp[x][t_idxx] = board[x][y];
				}
			}
		}
	}

	//마지막으로 복사해주고 끝
	for (int x = 1;x <= N;x++) {
		for (int y = 1; y <= N; y++) {
			board[x][y] = temp[x][y];
		}
	}
}

void right() {
	int temp[21][21] = { 0, };
	int canjoin[21][21] = { 0, };//yes가 0 no가 1


	for (int x = 1; x <= N;x++) {
		int t_idxx = 0;//들어온 원소 수라고 생각 최초는 empthy
	
		for (int y = N; y >= 1; y--) {

			if (board[x][y] == 0) continue;

			//board[x][y]에 뭔가 있을때..
			if (t_idxx == 0) {//처음껀 그냥 옮겨주고
				t_idxx++;
				temp[x][N + 1 - t_idxx] = board[x][y];
			}
			else {//나머지의 경우는 같은거 있는지 검사
				if (temp[x][N + 1 - t_idxx] == board[x][y] && canjoin[x][N + 1 - t_idxx] == 0) {
					temp[x][N + 1 - t_idxx] = temp[x][N + 1 - t_idxx] * 2;
					//t_idxx는 그대로 유지
					canjoin[x][N + 1 - t_idxx] = 1;
				}
				else {
					t_idxx++;
					temp[x][N + 1 - t_idxx] = board[x][y];
				}
			}
		}
	}

	//마지막으로 복사해주고 끝
	for (int x = 1;x <= N;x++) {
		for (int y = 1; y <= N; y++) {
			board[x][y] = temp[x][y];
		}
	}
}

//동치 분석으로 인한 dfs코드
void dfs(int count) {
    int backup_board[21][21] = { 0 };//backtrack을 위해 필요함
    
	if (count == 5) {//재귀의 탈출조건(중요)
		int candi = find_max();
		ans = MAX(ans, candi);

		return;
	}


	for (int i = 1;i <= 4;i++) {//1=상, 2=하, 3=좌, 4=우
        memcpy(backup_board, board, sizeof(board));//저장해 놓고
		switch (i)
		{
		case 1:
			up();
			break;
		case 2:
			down();
			break;
		case 3:
			left();
			break;
		case 4:
			right();
			break;
		default:
			break;
		}
		dfs(count + 1);
		memcpy(board, backup_board, sizeof(backup_board));//해당 dfs후 backtrack하기
	}

}




int main() {
	cin >> N;
	for (int x = 1; x <= N;x++) {
		for (int y = 1; y <= N;y++) {
			cin >> board[x][y];
		}
	}

	int count = 0;
	dfs(count);

	cout << ans;
}

seico75 4년 전 1

저도 덕분에 공부 많이 했고 만드신 소스 아이디어로 제 코드도 업그레이드 했네요. 다음엔 hard도 도전해보시죠.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

2048 게임 12100번 질문입니다...SW역량 Test 기출

lawliet777 4년 전 1

seico75 4년 전 1

lawliet777 4년 전 0

lawliet777 4년 전 0

seico75 4년 전 1

seico75 4년 전 1

lawliet777 4년 전 0

seico75 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말