백준 17406 배열 돌리기4

출처: www.acmicpc.net/problem/17406

분류: 완전탐색

---

접근방식

주어진 rcs 의 순열을 뽑아주고 주어진 대로 잘 구현하면 되는 문제였습니다.

아직 순열이 익숙하지 않으시다면 여기로 :)

 

완전탐색의 문제는 늘 그렇죠. 알겠는데 어케 구현하냐.......

머리가 안 돌아가서 배열 돌리는 데 한참이 걸렸습니다 😭

이건 뭐 다른 방법보다 직접 해보면서 익숙해지는 게 최선 같아요

저는 미리 회전할 부분을 카피해놓고 사이즈별로 위, 아래, 오른쪽, 왼쪽을 각각 포문돌면서 밀어주는 방식으로 구현했씁니다.

 

처음에 회전할 부분만 그 크기만큼의 배열로 복사해놓고, 그부분을 또 계산해서 하는 방식으로 했는데요...

그냥 굳이 다른 크기의 배열에 힘들게 복사해서 계산하지 말고 원복 배열을 그대로 카피해놓고 하면 훨씬 간단하면서도 빠르게 구할 수 있습니다...

하 전 왜 이렇게 했을까요 😳🤯

처음에 회전할 크기만큼 복사해놓고 하기 ( 248ms )

func rotate(_ rcs: [Int], metrix: inout [[Int]]) {
    let row = rcs[0]-1
    let col = rcs[1]-1
    let size = rcs[2]
    
    var origin = [[Int]](repeating: [Int](repeating: 0, count: rcs[2]*2+1), count: rcs[2]*2+1)
    
    for r in 0..<origin.count {
        for c in 0..<origin.count {
            origin[r][c] = metrix[r+row-rcs[2]][c+col-rcs[2]]
        }
    }
    
    for s in 1...rcs[2] {
        // 위
        for originC in size-s..<origin.count-size+s-1 {
            metrix[row-s][(originC + col-size) + 1] = origin[size-s][originC]
        }
        
        // 아래
        for originC in (size-s+1..<origin.count-size+s).reversed() {
            metrix[row+s][(originC + col-size) - 1] = origin[size+s][originC]
        }
        
        // 오른쪽
        for originR in size-s..<origin.count-size+s-1 {
            metrix[(originR + row-size) + 1][col+s] = origin[originR][size+s]
        }
        
        // 왼쪽
        for originR in (size-s+1..<origin.count-size+s).reversed() {
            metrix[(originR + row-size) - 1][col-s] = origin[originR][size-s]
        }
    }
}

 

그냥 원본 배열 복사 ( 60 ms )

시간도 훨씬 짧고 코드도 훨씬 간단하죠.... 

func rotate(_ rcs: [Int], metrix: inout [[Int]]) {
    let row = rcs[0]-1
    let col = rcs[1]-1
    
    let origin = metrix
    
    for s in 1...rcs[2] {
        // 위
        for c in col-s..<col+s {
            metrix[row-s][c+1] = origin[row-s][c]
        }
        
        // 아래
        for c in (col-s+1...col+s).reversed() {
            metrix[row+s][c-1] = origin[row+s][c]
        }
        
        // 오른쪽
        for r in row-s..<row+s {
            metrix[r+1][col+s] = origin[r][col+s]
        }
        
        // 왼쪽
        for r in (row-s+1...row+s).reversed() {
            metrix[r-1][col-s] = origin[r][col-s]
        }
    }
}

 

(크게크게 보기... 메모 ... ✍️)

 

이렇게 회전 함수를 구현했다면 rcs 의 순열 대로 회전시키고 결과 값을 구해주면 됩니다!

 

해결방법

let nmk = readLine()!.split(separator: " ").map { Int(String($0))! }
var metrix = [[Int]]()
var rcsList = [[Int]]()
var minResult = 50 * 50 * 101

for _ in 0..<nmk[0] {
    metrix.append(readLine()!.split(separator: " ").map { Int(String($0))! })
}

for _ in 0..<nmk[2] {
    rcsList.append(readLine()!.split(separator: " ").map { Int(String($0))! })
}

func rotate(_ rcs: [Int], metrix: inout [[Int]]) {
    let row = rcs[0]-1
    let col = rcs[1]-1
    
    let origin = metrix
    
    for s in 1...rcs[2] {
        // 위
        for c in col-s..<col+s {
            metrix[row-s][c+1] = origin[row-s][c]
        }
        
        // 아래
        for c in (col-s+1...col+s).reversed() {
            metrix[row+s][c-1] = origin[row+s][c]
        }
        
        // 오른쪽
        for r in row-s..<row+s {
            metrix[r+1][col+s] = origin[r][col+s]
        }
        
        // 왼쪽
        for r in (row-s+1...row+s).reversed() {
            metrix[r-1][col-s] = origin[r][col-s]
        }
    }
}

func checkArray() {
    var copy = metrix
    for rcs in rcsList {
        rotate(rcs, metrix: &copy)
    }
    
    let arrayValue = copy.map({ $0.reduce(0, +) }).min()!
    
    if arrayValue < minResult {
        minResult = arrayValue
    }
}

func selectRcs(_ idx: Int) {
    guard idx < rcsList.count else {
        checkArray()
        return
    }
    
    for i in idx..<rcsList.count {
        rcsList.swapAt(i, idx)
        selectRcs(idx+1)
        rcsList.swapAt(i, idx)
    }
}


selectRcs(0)
print(minResult)

 

배운점

갈 길이 멀다...