백준 12100 2048 (easy)

작성일 | In |

Problem : 2048 (easy)

유형 : DFS

문제, 예제 입출력 설명

설명하기에 이미지가 많아서 문제 링크로 대체합니다

해결 전략

완전탐색이지만, 어떻게 탐색을 해야 할지 고민해보아야한다.
나의 경우 deque 자료구조를 이용했다.

움직이는 방향에 맞춰서 deque에 순차적으로 push 한다.
이때 원소는 {숫자, 합쳐짐 여부} 로 설정하였다.
0으로 표현되는 빈칸의 경우에는 의미가 없으니 deque에 넣지 않았다.
만약 맨 마지막에 들어간 숫자가, 현재 숫자와 같고 합쳐진적이 없다면
맨 마지막의 숫자를 빼고, 두 배를 한뒤 합쳐진적이 있다고 표시하고 다시 넣었다.

주의할 점

  • deque를 사용할 경우, front와 back을 헷갈리지 말자

풀이

DFS

  • 5번 움직였다면, 최대 숫자를 찾고 dfs를 종료한다.
  • 5번 움직이지 않았다면
    • 현재 상태을 따로 백업해둔다.
    • 방향에 맞춰서 돌려준다.
    • dfs 깊이를 증가시키고, 다음 dfs를 진행하러 간다.

방향에 맞춰 움직여준다.

  • 방향에 맞춰 deque에 차례대로, 원소를 넣는다.
  • 작업이 끝난뒤 남은 공간은 0으로 채워준다.

(다른 풀이) 방향에 맞춰서 움직일때, 게임판 자체를 돌린다.

  • 새로운풀이 코드
  • 2020-03-08 추가
  • 상, 하 , 좌 , 우 의 경우를 전부 따로 처리하지 않고,
  • 게임판 자체를 돌린다음, 한쪽방향 으로만 움직이게 한다.
    • 예시 좌측으로 밀어 넣는 경우만 구현해놓고
      • 게임판을 우측으로 90도 돌리고, 좌측으로 밀어버린다면
      • 기존 게임판에서 아래로 밀어버리는 결과를 낳게된다.

Deque를 채운다.

  • {숫자, 합쳐짐 여부} 여부로 채운다.
  • 맨 마지막에 들어간 숫자가, 현재 숫자와 같고 합쳐진적이 없다면
    • 맨 마지막의 숫자를 빼고, 두 배를 한뒤 합쳐진적이 있다고 표시하고 다시 넣는다.
  • 맨 마지막에 들어간 숫자가, 현재 숫자와 다르거나 합쳐진적이 있다면
    • 현재 숫자를 합쳐짐 표시를 하지않고 넣는다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <bits/stdc++.h>
#define pp pair<int, bool>
using namespace std;

int board[21][21];
int n, answer;
deque<pp> dq;

void output() {
    cout << "\n";
    for (int i = 0; i < n; ++i) {
        for (int ii = 0; ii < n; ++ii)cout << board[i][ii] << " ";
        cout << "\n";
    }
}

void fill_q(int data) {
    if (data == 0)return;
    if (!dq.empty()) {
        if (dq.back().first == data && dq.back().second == false) {
            dq.pop_back();
            dq.push_back({ data * 2, true });
            return;
        }
    }
    dq.push_back({ data, false });
}

void move(int dir) {
    if (dir == 0) {
        for (int ii = 0; ii < n; ++ii) {
            for (int i = 0; i < n; ++i) fill_q(board[i][ii]);

            while ((int)dq.size() < n)dq.push_back({ 0,true });
            for (int i = 0; i < n; ++i) {
                board[i][ii] = dq.front().first; dq.pop_front();
            }
        }
    }

    else if (dir == 1) {
        for (int ii = 0; ii < n; ++ii) {
            for (int i = n-1; i >= 0; --i) fill_q(board[i][ii]);

            while ((int)dq.size() < n)dq.push_back({ 0,true });
            for (int i = n-1; i >=0; --i) {
                board[i][ii] = dq.front().first; dq.pop_front();
            }
        }
    }

    else if (dir == 2) {
        for (int i = 0; i < n; ++i) {
            for (int ii = 0; ii < n; ++ii) fill_q(board[i][ii]);

            while ((int)dq.size() < n)dq.push_back({ 0,true });
            for (int ii = 0; ii < n; ++ii) {
                board[i][ii] = dq.front().first; dq.pop_front();
            }
        }
    }

    else if (dir == 3) {
        for (int i = 0; i < n; ++i) {
            for (int ii = n-1; ii >= 0; --ii) fill_q(board[i][ii]);

            while ((int)dq.size() < n)dq.push_back({ 0,true });
            for (int ii = n-1; ii >= 0; --ii) {
                board[i][ii] = dq.front().first; dq.pop_front();
            }
        }
    }
}

void dfs(int move_cnt) {
    //output();
    if (move_cnt == 5) {
        for (int i = 0; i < n; ++i) {
            for (int ii = 0; ii < n; ++ii) answer = max(answer, board[i][ii]);
        }
        return;
    }

    int save_board[21][21] = { 0, };
    memcpy(save_board, board, sizeof(board));

    for (int dir = 0; dir < 4; ++dir) {
        move(dir);
        dfs(move_cnt + 1);
        memcpy(board, save_board, sizeof(board));
    }
}

void solve() {
    dfs(0);
}

void input() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        for (int ii = 0; ii < n; ++ii)   cin >> board[i][ii];
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    //freopen("input.txt", "r", stdin);
    cin.tie(NULL);  cout.tie(NULL);

    input();
    solve();
    cout << answer;
    return 0;
}

코드2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <bits/stdc++.h>
#define pp pair<bool, int>
#define merge first
#define data second
using namespace std;

int board[21][21];
int n;
int answer;

void move(int i) {
    deque<pp> q;

    for (int ii = 0; ii < n; ++ii) {
        if (board[i][ii] == 0)continue;
        
        if (!q.empty()) {
            if (q.back().merge == false && q.back().data == board[i][ii]) {
                q.pop_back();
                q.push_back({ true, board[i][ii] * 2 });
                continue;
            }
        }
        q.push_back({ false, board[i][ii] });
    }
    
    while (q.size() < n) {
        q.push_back({ false, 0 });
    }

    for (int ii = 0; ii < n; ++ii) {
        board[i][ii] = q.front().data;  q.pop_front();
    }
}

void rotate(int k) {
	int backup_board[21][21];

	while (k--) {
		memcpy(backup_board, board, sizeof(board));

		for (int i = 0; i < n; ++i) {
			for (int ii = 0; ii < n; ++ii) {
				board[i][ii] = backup_board[(n - 1) - ii][i];
			}
		}
	}

}

void find_max() {
    for (int i = 0; i < n; ++i) {
        for (int ii = 0; ii < n; ++ii)
            answer = max(answer, board[i][ii]);
    }
}

void dfs(int move_cnt) {
    if (move_cnt == 5) {
        find_max();
        return;
    }

    int backup_board[21][21];
    memcpy(backup_board, board, sizeof(board));

    for (int k = 0; k < 4; ++k) {
        rotate(k);
        for (int i = 0; i < n; ++i) move(i);

        dfs(move_cnt + 1);
        memcpy(board, backup_board, sizeof(board));
    }
}

void solve() {
    dfs(0);
    cout << answer << "\n";
}

void input() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        for (int ii = 0; ii < n; ++ii)  cin >> board[i][ii];
    }
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);
    //freopen("input.txt", "r", stdin);

    input();
    solve();

    return 0;
}

피드백

만약 새로운 원소가 들어 올때 deque의 front가 아닌 back을 확인해야함.
계속 front를 확인하고 있어서 애매하게 이상한 값이 나왔다.

눈버깅 하다가 30분 넘게 못 찾으면, 그냥 단계 별로 콘솔에 찍어보자.