문제 분석
예를 들어
2 2 2
4 4 4
8 8 8
이 주어지고
왼쪽으로 이동할때는
4 2 0
8 4 0
16 8 0
의 결과가 나와야 하는데 이러한 결과에 착안해서 해당입력에서 왼쪽으로 이동할때는 왼쪽부터 계산해야한다는 순서가 필요합니다.
좀더 도식화를 시키고 보면
a b c
d e f
h i j
왼쪽으로 이동할때
보는 순서는
(0,0)⇒(0,1):
a와 b가 같을때 (0,0) = a+b (0,1) = 0
a와 b가 다를때 (0,0) = a (0,1) = b
그러나 만약 a가 0이라면 (0,0) = b (0,1) = 0
그 다음은 (0,1)⇒(0,2):
b와 c가 같을때 (0,1) = b+c (0,2) = 0
b와 c가 다를때 (0,1) = b (0,2) = c
그러나 만약 b가 0이라면 (0,1) = c (0,2) = 0
그리고나서 이 해당 행이 끝나면
다음 행으로 가야합니다. d e f 역시 위와 같은 순서를 진행하고
다음 행 역시 그 방식으로 진행해야합니다.
이 방식이 제대로 먹히는 지 확인해보기 위해 여러가지 조건을 세웠습니다.
예시 1) 한 번의 이동에서 이미 합쳐진 블록은 또 합쳐질 수 없다
2 2 4 => 8 0 0 이 되어서는 안된다. 4 4 0 이 되야한다.
1.
4 0 4
2.
4 4 0
위 2가지 방식을 진행했을때 정상적으로 진행됨
예시 2) 똑같은 수가 세 개가 있는 경우에는 이동하려고 하는 쪽의 칸이 먼저 합쳐진다
2 2 2 => 0 2 4 가 되어서는 안되고 4 2 0 이 되야한다.
1.
4 0 2
2.
4 2 0
위 2가지 방식을 진행했을때 정상적으로 진행됨
왼쪽은 했으니
이제 오른쪽 이동이다
b와 c가 같을때 (0,2) = b+c (0,1) = 0
b와 c가 다를때 (0,2) = c (0,1) = b
그러나 만약 c가 0이라면 (0,2) = b (0,1) = 0
위로 이동
a와 d가 같을때(0,0) = a+d (1,0) = 0
a와 d가 다를때 (0,0) = a (1,0) = d
그러나 만약 a가 0이라면 (0,0) = d (1,0) = 0
이렇게 구현을 왼쪽,오른쪽,위쪽,아래쪽으로 이동했을 때의 연산을 각각 실행시키고 어느쪽이든간에 5번이 반복되어 실행되었으면 그 결과의 배열에서 최댓값을 리턴 하는 방식으로 코드를 짠다.
하지만 테스트케이스
2 2 2 2
2 2 2 2
2 2 2 2
2 2 2 2
첫줄을 보면 왼쪽으로 이동할때
=> 4 0 2 2
=> 4 2 0 2
=> 4 2 2 0
4 4 0 0
이 나와야 하는데
4 2 2 0
으로 실패
그래서 이 방식은 차용하돼 빈칸은 항상 뒤로 옮기는 방식으로 했습니다.
예를들어
2 2 2 2
=>4 0 2 2
가 나왔을때 0이 앞에 있으므로 2를 앞으로 땡겨서
4 2 2 0
으로 만들고 계산하면
4 4 0 0
으로 정상적으로 결과가 나옵니다.
즉 추가조건을 붙입니다.
a와 b가 같을때 (0,0) = a+b (0,1) = 0
\+ **(a와 b가 같을때는 무조건 0이 생기므로) 다음을 앞으로 땡긴다.**
a와 b가 다를때 (0,0) = a (0,1) = b
그러나 만약 a가 0이라면 (0,0) = b (0,1) = 0
이제 코드를 봅니다.
#include <iostream>
#include <algorithm>
using namespace std;
int N;
int arr[20][20];
int big = -1;
void 왼쪽이동()
{
//숫자들을 모두 왼쪽정렬을 한다.
//2의 배수의 개수를 센다 그리고 그만큼 집어넣는다.
for (int i = 0; i < N; i++)
{
//2의 배수를 채워넣을 위치
int pos = 0;
for (int j = 0; j < N; j++)
{
if (arr[i][j] != 0)
{
arr[i][pos++] = arr[i][j];
//pos의 위치가 그 자신인 경우는 0으로 초기화하면 안됨
//ex) 2 0 0 2 에서 pos가 0의 위치고 j=0이면 0으로 초기화 하면 안됨
if (pos - 1 == j)continue;
arr[i][j] = 0;
}
}
}
for (int j = 0; j < N; j++) {
for (int i = 0; i < N - 1; i++)
{
//a와 b가 같을때 합한다 그런데 그 위치에 0으로 만들었으므로 한칸씩 옮긴다.
if (arr[j][i] == arr[j][i + 1]) {
arr[j][i] = arr[j][i] + arr[j][i + 1];
arr[j][i + 1] = 0;
for (int k = i + 1; k < N - 1;k++)
{
arr[j][k] = arr[j][k + 1];
}
arr[j][N - 1] = 0;
}
else {
//만약 a가 0이라면
if (arr[j][i] == 0) {
arr[j][i] = arr[j][i + 1];
arr[j][i + 1] = 0;
}
else {
continue;
}
}
}
}
}
void 오른쪽이동()
{
//오른쪽 정렬을 한다.
for (int i = 0; i < N; i++)
{
//2의 배수를 채워넣을 위치
int pos = N-1;
for (int j = N-1; j >=0; j--)
{
if (arr[i][j] != 0)
{
arr[i][pos--] = arr[i][j];
if (pos + 1 == j)continue;
arr[i][j] = 0;
}
}
}
for (int j = 0; j < N; j++) {
for (int i = N - 1; i > 0; i--)
{
//b와 c가 같을때
if (arr[j][i] == arr[j][i - 1]) {
arr[j][i] = arr[j][i] + arr[j][i - 1];
arr[j][i - 1] = 0;
for (int k = i - 1; k >0;k--)
{
arr[j][k] = arr[j][k - 1];
}
arr[j][0] = 0;
}
else {
//만약 c가 0이라면
if (arr[j][i] == 0) {
arr[j][i] = arr[j][i - 1];
arr[j][i - 1] = 0;
}
else {
continue;
}
}
}
}
}
void 위로이동() {
//숫자들을 모두 위쪽정렬을 한다.
//2의 배수의 개수를 센다 그리고 그만큼 집어넣는다.
for (int i = 0; i < N; i++)
{
//2의 배수를 채워넣을 위치
int pos = 0;
for (int j = 0; j < N; j++)
{
if (arr[j][i] != 0)
{
arr[pos++][i] = arr[j][i];
if (pos - 1 == j)continue;
arr[j][i] = 0;
}
}
}
for (int j = 0; j < N; j++) {
for (int i = 0; i < N - 1; i++)
{
//a와 d가 같을때
if (arr[i][j] == arr[i + 1][j])
{
arr[i][j] = arr[i][j] + arr[i + 1][j];
arr[i + 1][j] = 0;
for (int k = i + 1; k < N - 1;k++)
{
arr[k][j] = arr[k+1][j];
}
arr[N-1][j] = 0;
}
else {
// a가 0이라면
if (arr[i][j] == 0) {
arr[i][j] = arr[i + 1][j];
arr[i + 1][j] = 0;
}
else {
continue;
}
}
}
}
}
void 아래이동() {
//아래로 정렬을 한다.
for (int i = 0; i < N; i++)
{
//2의 배수를 채워넣을 위치
int pos = N - 1;
for (int j = N - 1; j >= 0; j--)
{
if (arr[j][i] != 0)
{
arr[pos--][i] = arr[j][i];
if (pos + 1 == j)continue;
arr[j][i] = 0;
}
}
}
for (int j = 0; j < N; j++)
{
for (int i = N - 1; i > 0; i--)
{
if (arr[i][j] == arr[i - 1][j])
{
arr[i][j] = arr[i][j] + arr[i - 1][j];
arr[i - 1][j] = 0;
for (int k = i - 1; k > 0;k--)
{
arr[k][j] = arr[k-1][j];
}
arr[0][j] = 0;
}
else {
if (arr[i][j] == 0)
{
arr[i][j] = arr[i - 1][j];
arr[i - 1][j] = 0;
}
else {
continue;
}
}
}
}
}
void game(int step) {
if (step == 5) {
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
big = max(big, arr[i][j]);
}
}
return;
}
int copy_arr[20][20];
//일단 4번 방향 바뀌기전 복사
for (int i = 0; i < 20; i++) {
for (int j = 0; j < 20; j++) {
copy_arr[i][j] = arr[i][j];
}
}
//----------------------------
왼쪽이동();
game(step+1);
//원상복구
for (int i = 0; i < 20; i++) {
for (int j = 0; j < 20; j++) {
arr[i][j] = copy_arr[i][j];
}
}
오른쪽이동();
game(step + 1);
//원상복구
for (int i = 0; i < 20; i++) {
for (int j = 0; j < 20; j++) {
arr[i][j] = copy_arr[i][j];
}
}
위로이동();
game(step + 1);
//원상복구
for (int i = 0; i < 20; i++) {
for (int j = 0; j < 20; j++) {
arr[i][j] = copy_arr[i][j];
}
}
아래이동();
game(step + 1);
//원상복구
for (int i = 0; i < 20; i++) {
for (int j = 0; j < 20; j++) {
arr[i][j] = copy_arr[i][j];
}
}
}
int main() {
cin >> N;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
cin >> arr[i][j];
}
}
game(0);
cout << big;
}'Algorithm > BOJ' 카테고리의 다른 글
| [백준 16236] 아기상어 (0) | 2023.05.07 |
|---|---|
| [백준 1475] 방번호 (0) | 2023.05.03 |
| [백준 14500] 테트로미노 (0) | 2023.05.02 |
| [백준 15683] 감시 (1) | 2023.04.30 |
| [백준 1005] ACM Craft (0) | 2023.04.29 |