백준 12100번 - 2048 (Go)

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

분석

이 문제는 4방향으로 최대 5번의 이동을 하는 시뮬레이션 문제입니다.

시간 복잡도는 1 <= n <= 20 이므로, O(n^2 * 4^5) = 400 * 1024 = 약 400,000 으로 여유롭습니다.

공간 복잡도는 재귀 할때마다 새 보드를 생성하므로, int 형 O(n^2 * 5) = 8byte * 400 * 5 = 16,000 으로 여유롭습니다.

 

알고리즘을 생각해보면,

 

1. 방향 탐색 (재귀/백트래킹):
   • 상, 하, 좌, 우 4가지 방향으로 5번 이동하는 모든 경로를 재귀 함수로 탐색합니다.
   • 각 단계마다 격자 상태를 복사해서 넘겨주어야 원본 데이터가 유지 됩니다.
2. 블록 밀기 (Move):
   • 한 방향으로 밀 때, "이미 합쳐진 블록은 이번 턴에 다시 합쳐질 수 없다"는 규칙이 가장 중요합니다.
   • 예: 2 2 2 2가 한 방향으로 밀리면 8이 아니라 4 4가 되어야 합니다.
   • 한 줄씩 꺼내서 0이 아닌 숫자들만 모은 뒤, 앞에서부터 짝이 맞으면 합치고 새 배열에 담는 방식을 구현합니다.

 

풀이 코드

package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
)

var (
	n int
	res = math.MinInt32
)

func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	fmt.Fscan(in, &n)

	board := make([][]int, n)
	for i := 0; i < n; i++ {
		board[i] = make([]int, n)

		for j := 0; j < n; j++ {
			fmt.Fscan(in, &board[i][j])
		}
	}

	solution(0, board)

	fmt.Fprintln(out, res)
}

func solution(cnt int, curBoard [][]int) {
	if cnt == 5 {
		for i := 0; i < n; i++ {
			for j := 0; j < n; j++ {
				if curBoard[i][j] > res {
					res = curBoard[i][j]
				}
			}
		}
		
		return
	}

	for d := 0; d < 4; d++ {
		nextBoard := move(d, curBoard)
		solution(cnt + 1, nextBoard)
	}
}

func move(dir int, board [][]int) [][]int {
	newBoard := make([][]int, n)
	for i := range newBoard {
		newBoard[i] = make([]int, n)
	}

	switch dir {
	case 0:
		for i := 0; i < n; i++ {
			var temp []int

			for j := 0; j < n; j++ {
				if board[j][i] != 0 {
					temp = append(temp, board[j][i])
				}
			}

			sum := combine(temp)
			for j := 0; j < len(sum); j++ {
				newBoard[j][i] = sum[j]
			}
		}
	case 1:
		for i := 0; i < n; i++ {
			var temp []int

			for j := n - 1; j >= 0; j-- {
				if board[j][i] != 0 {
					temp = append(temp, board[j][i])
				}
			} 

			sum := combine(temp)
			for j := 0; j < len(sum); j++ {
				newBoard[n - 1 - j][i] = sum[j]
			}
		}
	case 2:
		for i := 0; i < n; i++ {
			var temp []int

			for j := 0; j < n; j++ {
				if board[i][j] != 0 {
					temp = append(temp, board[i][j])
				}
			}

			sum := combine(temp)
			for j := 0; j < len(sum); j++ {
				newBoard[i][j] = sum[j]
			}
		}
	case 3:
		for i := 0; i < n; i++ {
			var temp []int

			for j := n - 1; j >= 0; j-- {
				if board[i][j] != 0 {
					temp = append(temp, board[i][j])
				}
			}

			sum := combine(temp)
			for j := 0; j < len(sum); j++ {
				newBoard[i][n - 1 - j] = sum[j]
			}
		}
	}

	return newBoard
}

func combine(temp []int) []int {
	var sum []int

	for i := 0; i < len(temp); i++ {
		if i + 1 < len(temp) && temp[i] == temp[i + 1] {
			sum = append(sum, temp[i] * 2)
			i++
		} else {
			sum = append(sum, temp[i])
		}
	}

	return sum
}

회고

이동 후 합치는 과정에서 배열의 크기를 잘못 생각해서 많이 복잡했던 것 같습니다.

그리고 재귀마다 새배열을 만들어야 원본이 유지되기 때문에 구현하는데 있어서 주의할 점이 많았습니다.