문제
https://www.acmicpc.net/problem/12100
풀이
이 문제도 구현에 초점이 맞춰진 문제여서 (완전탐색이 가능한 조건임) 완전 탐색으로 풀었다. 먼저 이동하는 함수인 move, 병합하는 함수인 merge를 사용해서 move-merge-move를 하면 하나의 action을 수행하도록 했다. 방향은 따로 매개변수 action을 둬서 방향마다 다르게 동작하도록 만들었다. merge는 해당 방향의 가장 끝에 있는 것부터 옆에 있는 것을 합치게 만들었고 이때 생기는 빈틈을 move를 한번더 수행함으로써 처리한다.
풀이 자체는 깔끔하게 접근한 것 같은데 아래의 실수에서 시간이 좀 걸린것 같다. 그래도 전문제보단 나아졌다.
걸린 시간 : 1시간 7분 24초
다른 분은 하나씩 옮기고 같은 숫자를 만나면 합치고 또 합칠때 이미 합친거면 합치지 않게 해서 풀었다고 한다. 근데 코드 길이를 봐서 큰 차이는 없는 것 같아 취향 차이 일 것 같다.
실수
- 이번에 바뀐 matrix 상태를 원래 상태로 되돌리는 과정이 필요했는데 이걸 전역변수로 처리해서 있으나 마나한 데이터를 만들었다. 추후에 함수 내부에 만듬으로써 함수마다 하나의 원본을 저장하도록 수정했다.
- 최대값을 무지성으로 마지막에 끝나고 matrix를 확인해서 했는데 이렇게 하면 cnt가 5에 도달했는데 더 큰 최대값을 가지지만 마지막에 없는 것을 처리하지 못하기 때문에 cnt가 5가 되는 순간마다 전체 탐색하고 최대값을 저장하도록 코드를 수정했다.
- 백준 질문의 반례를 통해 모든 과정을 출력하면서 알았는데 move의 원래 if문의 순서는 up-down-right-left의 순서였다. 하지만 막상 돌려보니 실제로 작동하는 것은 left-right-down-up이여서 그렇게 수정했다... 다시보니까 생각을 잘못한 것 같다. 다음에는 좀더 자세히 보고나 함수를 작성하고 제대로 작동하는지 unit test를 해야되나 라는 생각이 든다. (이런 완탐 문제의 경우에는 경우의 가짓수가 많고 원하는 경로로 확인하기가 힘들어서 그냥 전부 출력하고 백트래킹하면서 오류를 파악하는 식으로 해야되지 않나 생각이 든다)
코드
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <utility>
using namespace std;
#define UP 0
#define DOWN 1
#define RIGHT 2
#define LEFT 3
vector<vector<pair<int, int>>> matrix(20, vector<pair<int, int>>(20, make_pair(0, 0))); // (값, 변경 여부)
int n, res = 0;
void move(int action) {
// 탐색 순서는 큰 상관 없음. 간 방향만 고려하면 됨. (하나의 축의 방향만 고려)
if (action == LEFT) {
vector<int> last_location(20, -1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j].first != 0) {
matrix[i][last_location[i] + 1].first = matrix[i][j].first;
((last_location[i] + 1 == j) ? (matrix[i][j].first) : (matrix[i][j].first = 0)); // 같으면 아무것도 안함
last_location[i]++;
}
}
}
}
else if (action == RIGHT) {
vector<int> last_location(20, n);
for (int i = 0; i < n; i++) {
for (int j = n - 1; j >= 0; j--) {
if (matrix[i][j].first != 0) {
matrix[i][last_location[i] - 1].first = matrix[i][j].first;
((last_location[i] - 1 == j) ? (matrix[i][j].first) : (matrix[i][j].first = 0)); // 같으면 아무것도 안함
last_location[i]--;
}
}
}
}
else if (action == DOWN) {
vector<int> last_location(20, n);
for (int i = n - 1; i >= 0; i--) {
for (int j = 0; j < n; j++) {
if (matrix[i][j].first != 0) {
matrix[last_location[j] - 1][j].first = matrix[i][j].first;
((last_location[j] - 1 == i) ? (matrix[i][j].first) : (matrix[i][j].first = 0)); // 같으면 아무것도 안함
last_location[j]--;
}
}
}
}
else if (action == UP) {
vector<int> last_location(20, -1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j].first != 0) {
matrix[last_location[j] + 1][j].first = matrix[i][j].first;
((last_location[j] + 1 == i) ? (matrix[i][j].first) : (matrix[i][j].first = 0)); // 같으면 아무것도 안함
last_location[j]++;
}
}
}
}
}
void merge(int action) {
if (action == UP) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j].second == 0 && i + 1 < n && matrix[i + 1][j].first != 0 && matrix[i][j].first == matrix[i + 1][j].first) { // 과한 처리긴 한데 돌아가니까 냅둠
matrix[i][j].second = 1;
matrix[i + 1][j].second = 1;
matrix[i][j].first += matrix[i + 1][j].first;
matrix[i + 1][j].first = 0;
}
}
}
}
else if (action == DOWN) {
for (int i = n - 1; i >= 0; i--) {
for (int j = 0; j < n; j++) {
if (matrix[i][j].second == 0 && i - 1 >= 0 && matrix[i - 1][j].first != 0 && matrix[i][j].first == matrix[i - 1][j].first) { // 과한 처리긴 한데 돌아가니까 냅둠
matrix[i][j].second = 1;
matrix[i - 1][j].second = 1;
matrix[i][j].first += matrix[i - 1][j].first;
matrix[i - 1][j].first = 0;
}
}
}
}
else if (action == RIGHT) {
for (int j = n - 1; j >= 0; j--) {
for (int i = n - 1; i >= 0; i--) {
if (matrix[i][j].second == 0 && j - 1 >= 0 && matrix[i][j - 1].first != 0 && matrix[i][j].first == matrix[i][j - 1].first) { // 과한 처리긴 한데 돌아가니까 냅둠
matrix[i][j].second = 1;
matrix[i][j - 1].second = 1;
matrix[i][j].first += matrix[i][j - 1].first;
matrix[i][j - 1].first = 0;
}
}
}
}
else if (action == LEFT) {
for (int j = 0; j < n; j++) {
for (int i = 0; i < n; i++) {
if (matrix[i][j].second == 0 && j + 1 < n && matrix[i][j + 1].first != 0 && matrix[i][j].first == matrix[i][j + 1].first) { // 과한 처리긴 한데 돌아가니까 냅둠
matrix[i][j].second = 1;
matrix[i][j + 1].second = 1;
matrix[i][j].first += matrix[i][j + 1].first;
matrix[i][j + 1].first = 0;
}
}
}
}
}
void copy(int type, vector<vector<pair<int, int>>>& matrixTemp) { // 0: mat -> temp, 1: temp -> mat
if (type == 0) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
matrixTemp[i][j].first = matrix[i][j].first;
matrix[i][j].second = 0;
}
}
}
else if (type == 1) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
matrix[i][j].first = matrixTemp[i][j].first;
}
}
}
}
void print(int cnt, int action) {
printf("\n cnt : %d\n action: %d\n", cnt, action);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
printf("%d ", matrix[i][j].first);
}
printf("\n");
}
}
void bruteForce(int cnt) {
vector<vector<pair<int, int>>> matrixTemp(20, vector<pair<int, int>>(20, make_pair(0, 0))); // (값, 변경 여부)
if (cnt >= 5) {
int temp;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
temp = max(temp, matrix[i][j].first);
}
}
res = max(res, temp);
return;
}
else {
copy(0, matrixTemp); // dirty bit 초기화는 여기서
move(UP);
merge(UP);
move(UP);
bruteForce(cnt + 1);
copy(1, matrixTemp);
copy(0, matrixTemp); // dirty bit 초기화는 여기서
move(DOWN);
merge(DOWN);
move(DOWN);
bruteForce(cnt + 1);
copy(1, matrixTemp);
copy(0, matrixTemp); // dirty bit 초기화는 여기서
move(RIGHT);
merge(RIGHT);
move(RIGHT);
bruteForce(cnt + 1);
copy(1, matrixTemp);
copy(0, matrixTemp); // dirty bit 초기화는 여기서
move(LEFT);
merge(LEFT);
move(LEFT);
bruteForce(cnt + 1);
copy(1, matrixTemp);
}
}
int main() {
int temp;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &matrix[i][j].first);
}
}
bruteForce(0);
printf("%d", res);
return 0;
}
기록용 블로그