글 읽기 - 반례를 찾았는데 어디가 틀린건지 모르겠습니다 ㅠㅠ

ljh940102 5년 전 0

계속 안되다가 반례를 찾긴 찾았는데 뭐가 문제인지 모르겠습니다 ㅠㅠ

일단 방식은 dfs인데 완전 탐색으로 했습니다.

그래서 결론적으로 몇번 dfs를 불러오는가를 봤을때 1364번(4+16+64+256+1024) 불러오는걸 봐서는

완전 탐색은 잘 되는 것 같은데 왜 안되는지 모르겠습니다 ㅠㅠ

사실 해당 반례는 그냥 풀려고해도 잘 모르겠어서요 ㅠㅠ

뭐가 문제인지 알려주실수 있나유 ㅠㅠ

8 8 4 16 32 0 0 8 8 8

8 8 4 0 0 8 0 0 0 0

16 0 0 16 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 16

0 0 0 0 0 0 0 0 0 2

제 코드 -> 64
정답 -> 128

#include <iostream>
#include <algorithm>

using namespace std;
int map[21][21];
int moveX[4] = {0,1,0,-1}; // 북동남서
int moveY[4] = {-1,0,1,0};
int n,rtn;

void solve(int depth,int di,int p_map[21][21]);
void arr_copy(int map[21][21],int copy[21][21]);


int main() {

	cin >> n;

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

	int d = 0;
	
	solve(0, 0, map);
	solve(0, 1, map);
	solve(0, 2, map);
	solve(0, 3, map);
	cout << rtn;
}

void solve(int depth,int di, int p_map[21][21]) {
	bool visit[20][20] = { 0 };
	int mymap[21][21];
	
	arr_copy(p_map, mymap);
	
	if (depth == 1) {

		return;
	}

	// 굴린 방향 처리 부분
	if (di == 0) {
		for (int i = 1; i < n; i++) {
			for (int j = 0; j < n; j++) {
				int tempi = i + moveY[0]; // -1
				while (mymap[tempi][j] == 0 && tempi>0) { // 비어있는 구간 모두 이동
					tempi--;
				}
				if (mymap[i][j] != 0 && mymap[tempi][j] == mymap[i][j] && visit[tempi][j] == false) { // 숫자가 같고 이번에 이미 더해준 수가 아니라면
					mymap[tempi][j] += mymap[i][j];
					mymap[i][j] = 0;
					visit[tempi][j] = true;
				}
				else { // 이동하고났는데 그 수가 이미 더해진 수이거나 같은수가 아닌경우
					if (tempi+1 != i) { // 이동 
						if (mymap[tempi][j] == 0) {
							mymap[tempi][j] = mymap[i][j];
							mymap[i][j] = 0;
						}
						else {
							mymap[tempi + 1][j] = mymap[i][j];
							mymap[i][j] = 0;
						}
					}
				}
			}
		}
	}
	if (di == 1) {
		for (int j = n-2; j >= 0; j--) {
			for (int i = 0; i <n ; i++) {
				int tempj = j + moveX[1]; // 이동하려고 하는 곳

				while (mymap[i][tempj] == 0 && tempj < n) { // 비어있는 구간 모두 이동
					tempj++;
				}
				if (mymap[i][j] != 0 && mymap[i][tempj] == mymap[i][j] && visit[i][tempj] == false) { // 숫자가 같고 이번에 이미 더해준 수가 아니라면
					mymap[i][tempj] += mymap[i][j];
					mymap[i][j] = 0;
					visit[i][tempj] = true;
				}
				else { // 이동하고났는데 그 수가 이미 더해진 수이거나 같은수가 아닌경우
					if (tempj-1 != j) { // 제자리가 아니라면 이동
						mymap[i][tempj-1] = mymap[i][j];
						mymap[i][j] = 0;
					}
				}
			}
		}
	}
	if (di == 2) {
		for (int i = n-2; i >= 0; i--) {
			for (int j = 0; j < n; j++) {
				int tempi = i + moveY[2]; // 이동하려고하는 곳

				while (mymap[tempi][j] == 0 && tempi < n) { // 비어있는 구간 모두 이동
					tempi++;
				}
				if (mymap[i][j] != 0&&mymap[tempi][j] == mymap[i][j] && visit[tempi][j] == false) { // 숫자가 같고 이번에 이미 더해준 수가 아니라면
					mymap[tempi][j] += mymap[i][j];
					mymap[i][j] = 0;
					visit[tempi][j] = true;
				}
				else { // 이동하고났는데 그 수가 이미 더해진 수이거나 같은수가 아닌경우
					if (tempi - 1 != i) { // 이동 
						mymap[tempi-1][j] = mymap[i][j];
						mymap[i][j] = 0;
					}
				}
			}
		}

	}
	if (di == 3) {
		for (int j = 1; j < n; j++) {

			for (int i = 0; i <n; i++) {
				int tempj = j + moveX[3]; // 이동하려고 하는 곳

				while (mymap[i][tempj] == 0 && tempj > 0) { // 비어있는 구간 모두 이동
					tempj--;
				}
				if (mymap[i][j]!=0&&mymap[i][tempj] == mymap[i][j] && visit[i][tempj] == false) { // 숫자가 같고 이번에 이미 더해준 수가 아니라면
					mymap[i][tempj] = mymap[i][tempj]+mymap[i][j];
					mymap[i][j] = 0;
					visit[i][tempj] = true;
				}
				else { // 이동하고났는데 그 수가 이미 더해진 수이거나 같은수가 아닌경우
					if (tempj + 1 != j) { // 제자리가 아니라면 이동
						if (mymap[i][tempj] == 0) {
							mymap[i][tempj] = mymap[i][j];
							mymap[i][j] = 0;
						}
						else {
							mymap[i][tempj + 1] = mymap[i][j];
							mymap[i][j] = 0;
						}
					}
				}
			}
		}
	}

	// 최대값 저장
	int temp = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (temp < mymap[i][j]) {
				temp = mymap[i][j];
			}
		}
	}
	if (rtn < temp) {
		rtn = temp;
	}
	//cout << depth << "번째 \n";
	//for (int i = 0; i < n; i++) {
	//	for (int j = 0; j < n; j++) {
	//		cout << mymap[i][j] << " ";
	//	}
	//	cout << "\n";
	//}
	//cout << "\n";


	//	 굴림 처리 후 다시 4방향 dfs 호출
	for (int direc = 0; direc < 4; direc++) {
		solve(depth + 1, direc, mymap);
	}
}

void arr_copy(int map[21][21], int copy[21][21]) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			copy[i][j] = map[i][j];
		}
	}
}

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

문제

문제

출처

ICPC

반례를 찾았는데 어디가 틀린건지 모르겠습니다 ㅠㅠ

ljh940102 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말