백준 17406 배열 돌리기 4

 

백준 17406 배열 돌리기 4

 

🪴 문제

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

17406번: 배열 돌리기 4

 

🪴 분류

accepted

3시간동안 풀었다.

2시간 반 코드 & 디버깅, 30분은 문제 잘못이해한거 고쳤다.

이 문제 반복 + 비슷한 유형 반복해 30분내로 풀 수 있도록 해야겠다!

(비슷한 유형 문제로는 프로그래머스, 나선형 어쩌구.. 떠오른다.)

 

🪴 문제풀이

문제 대충 읽고 회전 연산 들어오는 순서대로 회전하고 행 최소값을 찾는 문제인줄 알았다.

하지만, '틀렸습니다' 결과를 보고 문제를 다시 읽으니

회전 연산의 순서는 임의로 정해도 되며, 모든 회전 연산을 1번씩 수행한 후, 최소값을 찾는 문제였다.

순서가 중요하므로 순열 라이브러리를 사용했다.

 

 - 회전 시작점과 동남서북 돌고 다시 시작점으로 돌아왔을 때, 끝나는 재귀함수

 - 시작점을 변경하며 회전해야하는 횟수 규칙 찾기, s*2+1, s*2+1-2, s*2+1-4, ... 1에 도달하는 횟수만큼 회전한다.

 - 회전 순서대로 회전 한 후, 최소값 업데이트

 

📜 나의 코드

from itertools import permutations
import copy

R, C, T = map(int, input().split())

maps = []
for _ in range(R):
    maps.append(list(map(int, input().split())))
    
global dr, dc
dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]

def rotation(fr, fc, cr, cc, d, val, maps):
    global s_r, s_c, e_r, e_c, dr, dc, visited

    nr,nc = cr+dr[d], cc+dc[d]
    # 다시 시작 점으로 돌아오면 끝내기!
    if nr==fr and nc==fc:
        visited[nr-s_r][nc-s_c] = True
        maps[nr][nc] = val
        return
    if 0<=nr-s_r<N and 0<=nc-s_c<N and not visited[nr-s_r][nc-s_c] and s_r<=nr<=e_r and s_c<=nc<=e_c:
        visited[nr-s_r][nc-s_c] = True
        next_val = maps[nr][nc]
        maps[nr][nc] = val
        rotation(fr, fc, nr, nc, d, next_val, maps)
    else:
    # 더 이상 갈 수 없으면 방향 바꿈
        d = (d+1)%4
        rotation(fr, fc, cr,cc,d,val, maps)

# 연산들
cals = []
for _ in range(T):
    # r, c, s = 3,4,2
    r, c, s = map(int, input().split())
    cals.append((r,c,s))

# 연산 순서 모든 경우의 수
answer = float('inf')
for i in permutations(cals, len(cals)):

    Maps = copy.deepcopy(maps)
    # print('연산전')
    # for e in Maps:
    #     print(e)
    # print()

    for j in list(i):    
        r, c, s = j

        N = s*2+1
        visited = [[False for _ in range(N)] for _ in range(N)]

        s_r, s_c = r-s-1, c-s-1
        e_r, e_c = r+s-1, r+c-1

        i = 0
        copyN = N
        while(copyN != 1):
            rotation(s_r+i, s_c+i, s_r+i, s_c+i, 1, Maps[s_r+i][s_c+i], Maps)
            i += 1
            copyN -= 2

        # print(r,c,s)
        # for e in Maps:
        #     print(e)
        # print()
    
    for e in Maps:
        answer = min(answer, sum(e))

    # print(answer)
    # print('-----------------')

print(answer)