[백준] 배열 돌리기 4 (17406번) Swift

문제 내용

N X M 사이즈의 배열이 주어진다.

회전 연산 K 개가 주어지고

주어진 회전 연산으로 회전을 하여 행의 최솟값을 구해라

회전 연산은 모두 한 번씩 사용, 순서는 임의로 정해도 된다. (모든 경우의 수로 하라는 뜻)

 

제한사항

• 3 ≤ N, M ≤ 50
• 1 ≤ K ≤ 6
• 1 ≤ A[i][j] ≤ 100
• 1 ≤ s
• 1 ≤ r-s < r < r+s ≤ N
• 1 ≤ c-s < c < c+s ≤ M

---

전체 코드

// 1. size (N, M, K 입력 받기)
let size = readLine()!.split { $0 == " " }.map { Int(String($0))! }
// 2. 원본 배열
var originArr: [[Int]] = Array(repeating: [], count: size[0])
// 3. 회전 연산 넣을 배열
var orders: [[Int]] = []
// 4. 결과
var result = Int.max

// 5. 배열을 읽어서 저장함
for i in 0..<size[0] {
    originArr[i] = readLine()!.split{ $0 == " " }.map{ Int(String($0))! }
}

// 6. 회전 연산을 읽어서 저장함
for _ in 0..<size[2] {
    let order = readLine()!.split { $0 == " " }.map{ Int(String($0))! }
    orders.append(order)
}


// 7. 값을 바꿀 배열 생성
var arr = originArr

// 8. 회전 연산 수 만큼 visit 함수 호출
for i in 0..<orders.count {
    visit([i])
}

// 9. visit 함수
func visit(_ indices: [Int]) {
    // 10. 만약 indices 에 들어있는 수가 orders 수와 같다면
    if indices.count == orders.count {
        // 11. 변경할 배열을 원본 배열로 설정해주고
        arr = originArr
        
        // 12. indices 만큼 반복함
        for index in indices {
            // 13. 해당하는 회전 연산을 불러오고
            let ord = orders[index]
            
            // 14. 회전 연산 진행함
            for i in 1...ord[2] {
                rotate(ord[0], ord[1], i)
            }
        }
        
        // 15. 변경된 배열에서 행 마다 최소값 최신화함
        for i in 0..<arr.count {
            result = min(result, arr[i].reduce(0, +))
        }
        return
    }
    
    // 16. 회전 연산 순서에 대한 모든 경우의 수를 위한 반복문
    for i in 0..<orders.count {
        if !indices.contains(i) {
            visit(indices + [i])
        }
    }
}


// 17. 회전 함수
func rotate(_ r: Int, _ c: Int, _ s: Int) {
    // 18. 먼저 배열의 각 모서리 (왼쪽 상단, 오른쪽 상단, 왼쪽 하단, 오른쪽 하단) 저장
    let edges = [arr[r - s - 1][c - s - 1],
                 arr[r - s - 1][c + s - 1],
                 arr[r + s - 1][c - s - 1],
                 arr[r + s - 1][c + s - 1]
    ]
    
    // 19. 배열의 가장 상단에 있는 것(Horizon)을 오른쪽으로 이동
    for i in stride(from: c + s - 2, through: c - s - 1, by: -1) {
        arr[r - s - 1][i + 1] = arr[r - s - 1][i]
    }
    
    // 20. 배열의 가장 우측에 있는 것(Vertical)을 아래로 이동
    for i in stride(from: r + s - 2, through: r - s - 1, by: -1) {
        arr[i + 1][c + s - 1] = arr[i][c + s - 1]
    }
    
    // 21. 배열의 가장 하단에 있는 것(Horizon)을 왼쪽으로 이동
    for i in c - s ... c + s - 1 {
        arr[r + s - 1][i - 1] = arr[r + s - 1][i]
    }
    
    // 22. 배열의 가장 좌측에 있는 것(Vertical)을 위로 이동
    for i in r - s ... r + s - 1 {
        arr[i - 1][c - s - 1] = arr[i][c - s - 1]
    }
    
    // 23. 각 엣지에 대해 위치 갱신함
    arr[r - s - 1][c - s] = edges[0]
    arr[r - s][c + s - 1] = edges[1]
    arr[r + s - 2][c - s - 1] = edges[2]
    arr[r + s - 1][c + s - 2] = edges[3]
}

print(result)

 

 

가장 핵심이 되는 것은 rotate 함수이다.

// 17. 회전 함수
func rotate(_ r: Int, _ c: Int, _ s: Int) {
    // 18. 먼저 배열의 각 모서리 (왼쪽 상단, 오른쪽 상단, 왼쪽 하단, 오른쪽 하단) 저장
    let edges = [arr[r - s - 1][c - s - 1],
                 arr[r - s - 1][c + s - 1],
                 arr[r + s - 1][c - s - 1],
                 arr[r + s - 1][c + s - 1]
    ]
    
    // 19. 배열의 가장 상단에 있는 것(Horizon)을 오른쪽으로 이동
    for i in stride(from: c + s - 2, through: c - s - 1, by: -1) {
        arr[r - s - 1][i + 1] = arr[r - s - 1][i]
    }
    
    // 20. 배열의 가장 우측에 있는 것(Vertical)을 아래로 이동
    for i in stride(from: r + s - 2, through: r - s - 1, by: -1) {
        arr[i + 1][c + s - 1] = arr[i][c + s - 1]
    }
    
    // 21. 배열의 가장 하단에 있는 것(Horizon)을 왼쪽으로 이동
    for i in c - s ... c + s - 1 {
        arr[r + s - 1][i - 1] = arr[r + s - 1][i]
    }
    
    // 22. 배열의 가장 좌측에 있는 것(Vertical)을 위로 이동
    for i in r - s ... r + s - 1 {
        arr[i - 1][c - s - 1] = arr[i][c - s - 1]
    }
    
    // 23. 각 엣지에 대해 위치 갱신함
    arr[r - s - 1][c - s] = edges[0]
    arr[r - s][c + s - 1] = edges[1]
    arr[r + s - 2][c - s - 1] = edges[2]
    arr[r + s - 1][c + s - 2] = edges[3]
}

 

먼저 edges 를 저장한다

 // 18. 먼저 배열의 각 모서리 (왼쪽 상단, 오른쪽 상단, 왼쪽 하단, 오른쪽 하단) 저장
    let edges = [arr[r - s - 1][c - s - 1],
                 arr[r - s - 1][c + s - 1],
                 arr[r + s - 1][c - s - 1],
                 arr[r + s - 1][c + s - 1]
    ]

좌측 상단, 우측 상단, 좌측 하단, 우측 하단 순으로 저장을 하였다.

 

그 다음 가장 상단에 있는 배열을 우측으로 이동시켰다.

// 19. 배열의 가장 상단에 있는 것(Horizon)을 오른쪽으로 이동
    for i in stride(from: c + s - 2, through: c - s - 1, by: -1) {
        arr[r - s - 1][i + 1] = arr[r - s - 1][i]
    }

stride 를 이용하여 우측으로 이동하였다.

 

그 다음으로는 가장 우측에 있는 배열을 아래로 이동시켰다.

    // 20. 배열의 가장 우측에 있는 것(Vertical)을 아래로 이동
    for i in stride(from: r + s - 2, through: r - s - 1, by: -1) {
        arr[i + 1][c + s - 1] = arr[i][c + s - 1]
    }

 

 

모두 진행을 하면

이런 모습이 된다.

회전하고 난 후 빈 공간에는 처음에 저장해둔 edges 의 값을 넣는다.

이렇게 테두리만 회전하는 것이 아닌 안쪽도 회전을 시켜야 한다

 

        // 12. indices 만큼 반복함
        for index in indices {
            // 13. 해당하는 회전 연산을 불러오고
            let ord = orders[index]
            
            // 14. 회전 연산 진행함
            for i in 1...ord[2] {
                rotate(ord[0], ord[1], i)
            }
        }

14 번에서 안쪽에서 바깥쪽으로 rotate 함수를 호출하고 있다.

바깥쪽 먼저 실행하고 안쪽을 실행하는 것이 아닌

안쪽 먼저 실행하고 바깥쪽 테두리를 회전시킨다.

순서가 어떻든 상관 없다.

---

결론

겉에 테두리만 회전하는 줄 알고 시간이 좀 걸렸다.

문제만 잘 읽고 조건에 맞춰 구현하면 쉽게 풀 수 있는 문제인 듯.

 

 

let array = Array(repeating: [], count: 10)

 

이런 식으로 배열을 생성하면 원래는 타입이 무엇인지 몰라서 에러가 났는데

이제는 Any 로 되네,, 신기방기쓰

 

 

let anyArray = [] // 타입 알려주세요 !

얘는 Any 타입으로 되는게 아니라 그냥 에러가 난다.

 

 

 

출처: 백준 17406번 배열 돌리기 4

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

17406번: 배열 돌리기 4