[BOJ] 17406번 : 배열 돌리기4(Go, Golang)

문제 링크 : 백준 17406번

[문제 접근]

전형적인 구현 문제이다.
회전 연산 정보의 모든 순서를 전부 해봐야하므로 조합을 통해 seq 슬라이스에 순서를 정해준다.
seq 사이즈가 k가 되면 회전을 시켜주는데 seq에 들어있는 순서대로 뽑아서 회전시켜야한다.
전부 회전시켜준뒤 최소 합을 찾아 정답을 갱신시켜준다.

[소스 코드]

package main

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

type node struct {
	r, c, s int
}

var (
	r       = bufio.NewReader(os.Stdin)
	w       = bufio.NewWriter(os.Stdout)
	n, m, k int
	arr     [51][51]int
	info    [6]node
	visit   [6]bool
	seq     []int
	ans     = 10000
)

func rotate() {
	temp := arr

	// seq 순서대로 돌리기
	for _, val := range seq {
		r := info[val].r
		c := info[val].c
		s := info[val].s

		for d := 1; d <= s; d++ {
			tmp := temp[r-d][c-d]
			// 왼쪽
			for i := r - d + 1; i <= r+d; i++ {
				temp[i-1][c-d] = temp[i][c-d]
			}
			// 아래쪽
			for i := c - d + 1; i <= c+d; i++ {
				temp[r+d][i-1] = temp[r+d][i]
			}
			// 오른쪽
			for i := r + d - 1; i >= r-d; i-- {
				temp[i+1][c+d] = temp[i][c+d]
			}
			// 위쪽
			for i := c + d - 1; i > c-d; i-- {
				temp[r-d][i+1] = temp[r-d][i]
			}
			temp[r-d][c-d+1] = tmp
		}
	}

	// 최소 합 찾기
	for i := 1; i <= n; i++ {
		sum := 0
		for j := 1; j <= m; j++ {
			sum += temp[i][j]
		}

		if ans == -1 || ans > sum {
			ans = sum
		}
	}
}

func cal(cnt int) {
	if cnt == k {
		rotate()
		return
	}
	for i := 0; i < k; i++ {
		if visit[i] {
			continue
		}
		seq = append(seq, i)
		visit[i] = true
		cal(cnt + 1)
		seq = seq[:len(seq)-1]
		visit[i] = false
	}
}

func main() {
	defer w.Flush()
	fmt.Fscan(r, &n, &m, &k)
	for i := 1; i <= n; i++ {
		for j := 1; j <= m; j++ {
			fmt.Fscan(r, &arr[i][j])
		}
	}
	for i := 0; i < k; i++ {
		var a, b, c int
		fmt.Fscan(r, &a, &b, &c)
		info[i] = node{r: a, c: b, s: c}
	}
	cal(0)
	fmt.Fprintln(w, ans)
}