[BOJ] 17406. 배열 돌리기 4

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

17406번: 배열 돌리기 4

 

 

1. 해결방법

r, c, s에 대한 모든 경우의 수를 2차원 배열에서 회전을 시켜야 하기 때문에 파이썬의 permutations 라이브러리를 사용하였다.

기본적으로 시계방향으로 회전하는 것이기 때문에 상하좌우 모두 값을 이동해주는 코드를 4개의 for문으로 해결하였고, 안 쪽 리스트도 이동해야해서 4개의 for문 위에 바로 s 값이 -1씩 되도록 반복해주었다.

1사이클이 돌면 2차원 배열의 각 row의 최솟값을 구하면 해결되는 문제이다.

아이디어를 생각하기는 쉬웠다. 
하지만 2차원 배열을 자유자제로 사용해야하는 부분에서 뇌가 많이 꼬이고 헷갈렸다.
또한, permutations이 포함된 for문에서 input으로 선언한 maps 2차원 배열이 초기화되지 않아서 깊은 복사인 deepcopy 함수를 사용해서 maps 값을 완전히 복사해서 해결하였다.

 

 

2. 정답코드

import sys
input = sys.stdin.readline
from itertools import permutations
from copy import deepcopy

N, M, K = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(N)]
k_list = [list(map(int, input().split())) for _ in range(K)]

min_v = sys.maxsize
def dfs():
    global min_v, graph

    for perm in permutations(k_list, K):
        maps = deepcopy(graph)
        for nr, nc, es in perm:
            for ns in range(es, 0, -1):
                start, end = [nr - ns - 1, nc - ns - 1], [nr + ns - 1, nc + ns - 1]

                temp_1 = maps[start[0]][start[1]]
                for i in range(start[1] + 1, end[1] + 1):
                    temp_2 = maps[start[0]][i]
                    maps[start[0]][i] = temp_1
                    temp_1 = temp_2

                for i in range(start[0] + 1, end[0] + 1):
                    temp_2 = maps[i][end[1]]
                    maps[i][end[1]] = temp_1
                    temp_1 = temp_2

                for i in range(end[1] - 1, start[1] - 1, -1):
                    temp_2 = maps[end[0]][i]
                    maps[end[0]][i] = temp_1
                    temp_1 = temp_2

                for i in range(end[0] - 1, start[0] - 1, -1):
                    temp_2 = maps[i][start[1]]
                    maps[i][start[1]] = temp_1
                    temp_1 = temp_2
        for row in maps:
            min_v = min(min_v, sum(row))

dfs()
print(min_v)