백준 17406번 - 배열 돌리기 4 (Go)

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

분석

이 문제는 완전탐색이고, 탐색 순서에 따라 결과가 바뀌니 순열 탐색 문제입니다.

시간복잡도는 순열생성 후 k 번 회전 수행, n * m 배열을 탐색해야하니 O(k! * (k * (n * m)) 입니다. 

3 <= n, m <= 50, 1 <= k <= 6 이므로 6! * 6 * 50 * 50 = 약 10,800,000 으로 여유롭습니다.

공간복잡도는 int형 2차원 배열 O(n * m) = 8 byte * 50 * 50 = 약 20 KB 로 여유롭습니다.

 

알고리즘 로직을 생각해보면,

 

1. 순열 (Permutation):
   • 회전 연산이 k개 주어질 때, 이를 나열하는 순서는 최대 k!가지입니다.
2. 배열 복사:
   • 각 순열 케이스마다 원본 배열이 변하면 안 되므로, 반드시 배열을 복사하여 시뮬레이션을 진행해야 합니다.
3. 배열 회전:
   • 주어진 r, c, s 에 대해 가장 바깥쪽 사각형부터 안쪽 사각형까지 순차적으로 돌립니다.
   • 한 칸씩 밀 때 값이 덮어씌워지지 않도록 임시 변수를 활용하거나 역순으로 당기는 처리가 필요합니다.
4. 값 계산:
   • 모든 회전이 끝난 후, 각 행의 합 중 최솟값을 구합니다.

 

풀이 코드

package main

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

type Operation struct {
	r, c, s int
}

var (
	n, m, k int
	grid [][]int
	operations []Operation
	visited []bool
	orders []int
	res = math.MaxInt32
)

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

	fmt.Fscan(in, &n, &m, &k)

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

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

	operations = make([]Operation, k)
	for i := 0; i < k; i++ {
		fmt.Fscan(in, &operations[i].r, &operations[i].c, &operations[i].s)
	}

	visited = make([]bool, k)
	orders = make([]int, k)

	permutaion(0)

	fmt.Fprintln(out, res)
}

func permutaion(depth int) {
	if depth == k {
		simulation()
		return
	}

	for i := 0; i < k; i++ {
		if !visited[i] {
			visited[i] = true
			orders[depth] = i
			permutaion(depth + 1)
			visited[i] = false
		}
	}
}

func simulation() {
	temp := make([][]int, n)
	for i := 0; i < n; i++ {
		temp[i] = make([]int, m)
		copy(temp[i], grid[i])
	}

	for _, idx := range orders {
		rotate(temp, operations[idx])
	}

	for i := 0; i < n; i++ {
		sum := 0

		for j := 0; j < m; j++ {
			sum += temp[i][j]
		}

		if sum < res {
			res = sum
		}
	}
}

func rotate(curGrid [][]int, operation Operation) {
	r, c, s := operation.r - 1, operation.c - 1, operation.s

	for i := 1; i <= s; i++ {
		top, bottom, left, right := r - i, r + i, c - i, c + i

		temp := curGrid[top][left]

		for i := top; i < bottom; i++ {
			curGrid[i][left] = curGrid[i + 1][left]
		}

		for i := left; i < right; i++ {
			curGrid[bottom][i] = curGrid[bottom][i + 1]
		}

		for i := bottom; i > top; i-- {
			curGrid[i][right] = curGrid[i - 1][right]
		}

		for i := right; i > left + 1; i-- {
			curGrid[top][i] = curGrid[top][i - 1]
		}

		curGrid[top][left + 1] = temp
	}
}

회고

순열 + 시뮬레이션 문제이고, 배열 인덱스 헷갈리지 말자.