백준 12100 2048 (Easy)

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

 

서론

어려움이 많았던 문제.

구현에 오류가 많았는데 테스트케이스는 하나 뿐이라

반례와 그 원인찾기가 무척 힘들었다.

 

발생했던 문제들은

1. 전역변수로 만들어진 지도를 여러 재귀에서 같이 사용했던 문제

2. 최대값 갱신을 블록이 이동할때마다 하는것이 아닌 5번째만 갱신했던 문제

3. 한번 합쳐진 숫자는 다시 합쳐지면 안되는것을 구현하면서 발생한 실수

 

---

풀이

여러 함수로 구성되어있다.

 

1. right(), left(), up(), down()

 

블록들을 이동시키는 함수다.

void up() {
	memset(visited, 0, sizeof(visited));
	int dir = 0; // 위
	for (int i = 1; i < n; i++) {
		for (int j = 0; j < n; j++) {
			dfs(i, j, dir);
		}
	}
	return;
}

visited는 합쳐진 블록을 다시 합치지 않기 위한 배열이며 한번 이동할때마다 초기화한다.

위와 같이 모든 칸(블록)을 반복문을 이용해서 특정 방향으로 이동시키는데, 구체적인 이동과 처리는 dfs함수가 담당한다.

각 함수는 반복문에서 시작과 끝이 다르다.

up()의 경우 열이 1부터 n-1까지 진행하며 (첫 행은 이동할 수 없으므로 이동하지 않는다.)

down()의 경우 열이 n-2부터 0까지 진행한다.

 

2. dfs()

 

블록들을 구체적으로 이동시키는 함수다.

1번 함수에서 특정 블록을 선택했으면 dfs()는 특정 블록을 특정 방향으로 dfs와 같이 다른 블록이나 벽을 만날때까지 이동시킨다. 

이동하면서 같은 값을 가지는 블록을 만나면 블록을 합친다.

void dfs(int y, int x, int dir) { // dir은 방향
	int ny = y + dy[dir]; // dir방향으로 한칸 전진
	int nx = x + dx[dir];

	if (ny >= n || nx >= n || ny < 0 || nx < 0) return; // 벽을 만나면 리턴

	if (map[ny][nx] == 0) { // 진행방향에 블록이 없으면 이동
		map[ny][nx] = map[y][x];
		map[y][x] = 0;
		visited[ny][nx] = visited[y][x];
		visited[y][x] = 0;
		dfs(ny, nx, dir);
	}
    // 진행방향에 합친적이 없고 같은 값의 블록이 있으면 합함
	else if (visited[ny][nx] == 0 && visited[y][x] == 0 && map[ny][nx] == map[y][x]) {
		map[ny][nx] = map[y][x] * 2;
		map[y][x] = 0;
		visited[y][x] = 0;
		visited[ny][nx] = 1;
		dfs(ny, nx, dir);
	}

	return;
}

 

3. bf()

 

4방향의 이동을 5번 실행하는 완전탐색 함수다.

재귀를 이용해서 구현했다.

완전탐색에서 전역변수의 사용은 조심해야한다. 완전탐색에서 재귀의 목적은 서로 다른 방향으로 전진해서 모든 경우의 수를 찾는 것인데 전역변수를 사용하게 되면 굳이 다른 방향으로 분리시킨 의미가 없어진다. map과 visited 배열을 전역변수로 만들어줬으므로, 각 재귀(idx 위치)시마다 map과 visited를 백업한 후 재귀(idx+1 위치)에서 리턴될때 수정된 지map과 visited를 백업한것으로 복구한다.

void bf(int idx, int select) {

	// 블록 이동, 4방향 중 하나를 선택한다.
	if (select == 0) right();
	else if (select == 1) left();
	else if (select == 2) up();
	else if (select == 3) down();

	// 지도복사
	int mapCopy[MAX_SIZE][MAX_SIZE] = { 0, };
	int visitedCopy[MAX_SIZE][MAX_SIZE] = { 0, };
	memcpy(mapCopy, map, sizeof(map));
	memcpy(visitedCopy, visited, sizeof(visited));

	// 최대값 갱신
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			result = max(result, map[i][j]);
		}
	}

	if (idx == 5) return; // 블록을 5번 이동했으면 리턴

	// 완전탐색
	for (int i = 0; i < 4; i++) {
		bf(idx + 1, i);
		// bf에서 리턴할때 기존 지도로 롤백
		memcpy(map, mapCopy, sizeof(map));
		memcpy(visited, visitedCopy, sizeof(visited));
	}
	return;
}

 

---

구현

// c++

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>

using namespace std;

#define MAX_SIZE 20

int n;
int map[MAX_SIZE][MAX_SIZE];
int visited[MAX_SIZE][MAX_SIZE];
int dy[4] = { -1, 0, 1, 0 };
int dx[4] = { 0, 1, 0, -1 };
int result;

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

void dfs(int y, int x, int dir) {
	int ny = y + dy[dir];
	int nx = x + dx[dir];

	if (ny >= n || nx >= n || ny < 0 || nx < 0) return;

	if (map[ny][nx] == 0) {
		map[ny][nx] = map[y][x];
		map[y][x] = 0;
		visited[ny][nx] = visited[y][x];
		visited[y][x] = 0;
		dfs(ny, nx, dir);
	}
	else if (visited[ny][nx] == 0 && visited[y][x] == 0 && map[ny][nx] == map[y][x]) {
		map[ny][nx] = map[y][x] * 2;
		map[y][x] = 0;
		visited[y][x] = 0;
		visited[ny][nx] = 1;
		dfs(ny, nx, dir);
	}

	return;
}

void up() {
	memset(visited, 0, sizeof(visited));
	int dir = 0;
	for (int i = 1; i < n; i++) {
		for (int j = 0; j < n; j++) {
			dfs(i, j, dir);
		}
	}
	return;
}

void right() {
	memset(visited, 0, sizeof(visited));
	int dir = 1;
	for (int i = 0; i < n ; i++) {
		for (int j = n - 2; j >= 0 ; j--) {
			dfs(i, j, dir);
		}
	}
	return;
}

void down() {
	memset(visited, 0, sizeof(visited));
	int dir = 2;
	for (int i = n - 2; i >= 0 ; i--) {
		for (int j = 0; j < n; j++) {
			dfs(i, j, dir);
		}
	}
	return;
}

void left() {
	memset(visited, 0, sizeof(visited));
	int dir = 3;
	for (int i = 0; i < n; i++) {
		for (int j = 1; j < n; j++) {
			dfs(i, j, dir);
		}
	}
	return;
}

void bf(int idx, int select) {

	if (select == 0) right();
	else if (select == 1) left();
	else if (select == 2) up();
	else if (select == 3) down();

	int mapCopy[MAX_SIZE][MAX_SIZE] = { 0, };
	int visitedCopy[MAX_SIZE][MAX_SIZE] = { 0, };
	memcpy(mapCopy, map, sizeof(map));
	memcpy(visitedCopy, visited, sizeof(visited));

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			result = max(result, map[i][j]);
		}
	}

	if (idx == 5) return;

	for (int i = 0; i < 4; i++) {
		bf(idx + 1, i);
		memcpy(map, mapCopy, sizeof(map));
		memcpy(visited, visitedCopy, sizeof(visited));
	}
	return;
}

int main() {
	init();
	bf(0, -1);
	cout << result;
}