백준 12100번: 2048(Python, cpp)

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

12100번: 2048 (Easy)

---

문제 해결을 위한 과정

이 문제의 경우 백트레킹 및 dfs 방식으로 해결할 수 있었다. dfs함수를 짜는 건 어렵지 않았지만 이동하는 함수 moveGraph 함수는 작성하기 어려웠다. 다만 차근차근 조건을 따져가며 작성하니 생각보다는 어렵지 않았던 문제였다. https://chldkato.tistory.com/163 이 분의 포스팅을 참조하여 소스코드를 작성하였다. 구현 유형을 조금 더 많이 접하여 친숙해진다면 보다 쉽게 해결할 수 있을것으로 기대된다.

---

소스코드 - python

import copy

def move(dir): # n e s w
    if dir == 0:
        for j in range(n):
            idx = 0
            for i in range(1, n):
                if graph[i][j] != 0: # if not 0
                    temp = graph[i][j]
                    graph[i][j] = 0
                    if graph[idx][j] == temp:
                        graph[idx][j] *= 2
                        idx += 1
                    elif graph[idx][j] == 0:
                        graph[idx][j] = temp  
                    elif graph[idx][j] != temp:
                        idx += 1
                        graph[idx][j] = temp
                        

    elif dir == 1:
        for i in range(n):
            idx = n-1
            for j in range(n-2, -1, -1):
                if graph[i][j] != 0: # if not 0
                    temp = graph[i][j]
                    graph[i][j] = 0
                    if graph[i][idx] == temp:
                        graph[i][idx] *= 2
                        idx -= 1
                    elif graph[i][idx] == 0:
                        graph[i][idx] = temp
                    elif graph[i][idx] != temp:
                        idx -= 1
                        graph[i][idx] = temp
                        
    
    elif dir == 2: # s
        for j in range(n):
            idx = n-1
            for i in range(n-2, -1, -1):
                if graph[i][j] != 0:
                    temp = graph[i][j]
                    graph[i][j] = 0
                    if graph[idx][j] == temp:
                        graph[idx][j] *= 2
                        idx -= 1
                    elif graph[idx][j] == 0:
                        graph[idx][j] = temp
                    elif graph[idx][j] != temp:
                        idx -= 1
                        graph[idx][j] = temp
                        

    elif dir == 3: # w
        for i in range(n):
            idx = 0
            for j in range(1, n):
                if graph[i][j] != 0:
                    temp = graph[i][j]
                    graph[i][j] = 0
                    if graph[i][idx] == temp:
                        graph[i][idx] *= 2
                        idx += 1
                    elif graph[i][idx] == 0:
                        graph[i][idx] = temp
                    elif graph[i][idx] != temp:
                        idx += 1
                        graph[i][idx] = temp
                        

def dfs(count):
    global ans, graph
    if count == 5: # 5인 경우
        for i in range(n):
            ans = max(ans, max(graph[i]))
        return

    copyGraph = copy.deepcopy(graph)
    for i in range(4):
        move(i)
        dfs(count + 1)
        graph = copy.deepcopy(copyGraph)
        

n = int(input())
graph = []
for _ in range(n):
  graph.append(list(map(int, input().split())))
ans = 0
dfs(0)
print(ans)

---

소스코드 - c++

#include <bits/stdc++.h>
#define MAX 21	
using namespace std;

int n;
int graph[MAX][MAX];
int ans;

void moveGraph(int dir) { // N, E, S, W
	if (dir == 0) {
		for (int j = 0; j < n; j++) {
			int idx = 0;
			for (int i = 1; i < n; i++) {
				if (graph[i][j] != 0) {
					int temp = graph[i][j];
					graph[i][j] = 0;
					if (graph[idx][j] == temp) {
						graph[idx][j] *= 2;
						idx += 1;
					}
					else if (graph[idx][j] == 0)
						graph[idx][j] = temp;
					else {
						idx += 1;
						graph[idx][j] = temp;
					}
				}
			}
		}
	}

	else if (dir == 1) {
		for (int i = 0; i < n; i++) {
			int idx = n-1;
			for (int j = n-2; j > -1; j--) {
				if (graph[i][j] != 0) {
					int temp = graph[i][j];
					graph[i][j] = 0;
					if (graph[i][idx] == temp) {
						graph[i][idx] *= 2;
						idx -= 1;
					}
					else if (graph[i][idx] == 0)
						graph[i][idx] = temp;
					else {
						idx -= 1;
						graph[i][idx] = temp;
					}
				}
			}
		}
	}

	else if (dir == 2) {
		for (int j = 0; j < n; j++) {
			int idx = n-1;
			for (int i = n-2; i > -1; i--) {
				if (graph[i][j] != 0) {
					int temp = graph[i][j];
					graph[i][j] = 0;
					if (graph[idx][j] == temp) {
						graph[idx][j] *= 2;
						idx -= 1;
					}
					else if (graph[idx][j] == 0)
						graph[idx][j] = temp;
					else {
						idx -= 1;
						graph[idx][j] = temp;
					}
				}
			}
		}
	}

	else {
		for (int i = 0; i < n; i++) {
			int idx = 0;
			for (int j = 1; j < n; j++) {
				if (graph[i][j] != 0) {
					int temp = graph[i][j];
					graph[i][j] = 0;
					if (graph[i][idx] == temp) {
						graph[i][idx] *= 2;
						idx += 1;
					}
					else if (graph[i][idx] == 0)
						graph[i][idx] = temp;
					else {
						idx += 1;
						graph[i][idx] = temp;
					}
				}
			}
		}
	}
}

void dfs(int count) {
	if (count == 5) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				ans = max(ans, graph[i][j]);
			}
		}
		return;
	}

	int copyGraph[MAX][MAX] = { 0, };
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			copyGraph[i][j] = graph[i][j];
		}
	}

	for (int k = 0; k < 4; k++) {
		moveGraph(k);
		dfs(count + 1);
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				graph[i][j] = copyGraph[i][j];
			}
		}
	}
}

int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> graph[i][j];
		}
	}
	dfs(0);
	cout << ans;
	return 0;
}