[Swift][BruteForce] 백준 14391번 (종이 조각)

요구 능력

BruteForce + recursiveFunction(DFS)

 

문제설명

가로와 세로를 섞어서 찢는데 나올 수 있는 가장 큰 수를 구하는 문제이다.

 

시간복잡도

종이조각을 가로로 자르거나 세로로 자르는 2가지의 경우가 모든칸에 적용될 수 있으므로

O(2^n)의 시간복잡도를 갖는다. n과 m이 최대4까지 나오니까 2^16이 최악의경우이다.

그리고 가로 혹은 세로로 찢어지는 경우마다 우리는 완전탐색을 해서 한번씩 들여다봐야하기 때문에

O(n *m)의 시간복잡도가 걸린다.

종합적으로 O(2^n * m * n)의 시간복잡도가 걸리는것이다.

DFS()

처음에는 이게 무슨뜻이지 싶었는데,

방문처리가 true로 처리됬을 경우에는 가로로 찢어진것을 의미하고,

방문처리가 false로 처리됬을 경우에는 세로로 찢어진것을 의미한다.

 

이게 무슨소린가 싶은사람도 분명히 있을 것이다.

이 문제를 풀 정도면 다들 백트래킹은 공부해본적이 있을것이다.

y == m의 경우 열의 끝에 갔을 때 줄을 바꿔서 탐색하기 위해 존재하는 것이다.

처음에 DFS는 돌 때 모든 visited는 true가 되서 모두 가로(visited[x][y] = true)로 두고 x == n까지 들어가게 된다.

그리고 다음번에 돌 때는 맨 마지막 스택에 쌓여있는 DFS()를 리턴하고 아래로 내려가서 visited[x][y] = false 처리가 될것이다.

만약 n = 4, m = 4라면 visited[3][3] = false가 되는것이다.

이렇게 되면 맨 마지막 원소만 세로로 찢는다는 말이다.

 

x==n에 들어가게되면 모든 열과행의 가로, 세로를 결정했다는 의미이다.

func dfs(_ x: Int, _ y: Int){
    if x == n {
        result = max(result, sum())
        return
    }
    
    if y == m{
        dfs(x + 1, 0)
        return
    }
//    print("x : \(x), y: \(y)")
    visited[x][y] = true
    dfs(x, y + 1)
    
    visited[x][y] = false
    dfs(x, y + 1)
}

 

sum()

행 또는 열 위주로 탐색을 해준다.

visited[row][col]이 true이면 가로로 계산을 해주다가 false가 나오면 세로를 의미하므로 계산을 멈추고 total에 더해준다.

그리고 sum=0으로 반드시 초기화해줘야한다. 가로로하는 계산의 끝을 만났기 때문이다.

이렇게 가로인 부분을 모두 탐색하고나면 마찬가지로 세로인 부분도 모두탐색해서 합을 구해주면 된다.

func sum() -> Int{
    var total = 0
    var sum = 0
    
    for row in 0..<n{
        sum = 0
        for col in 0..<m{
            if visited[row][col]{
                sum = (sum * 10) + arr[row][col]
            }else{
                total += sum
                sum = 0
            }
        }
        total += sum
    }
    
    
    for col in 0..<m{
        sum = 0
        for row in 0..<n{
            if !visited[row][col]{
                sum = (sum * 10) + arr[row][col]
            }else{
                total += sum
                sum = 0
            }
        }
        total += sum
    }
    return total
}

 

후기

보면 그냥 막막한문제인데 막상 풀고보면 원리는 이해하기쉬운문제이다.

혼자힘으로 풀지못한게 아쉽다.

import Foundation
let nm = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = nm[0]
let m = nm[1]
var arr = [[Int]]()
for _ in 0..<n{
    arr.append(readLine()!.map{Int(String($0))!})
}
var visited = Array(repeating: Array(repeating: false, count: m), count: n)
func sum() -> Int{
    var total = 0
    var sum = 0
    
    for row in 0..<n{
        sum = 0
        for col in 0..<m{
            if visited[row][col]{
                sum = (sum * 10) + arr[row][col]
            }else{
                total += sum
                sum = 0
            }
        }
        total += sum
    }
    
    
    for col in 0..<m{
        sum = 0
        for row in 0..<n{
            if !visited[row][col]{
                sum = (sum * 10) + arr[row][col]
            }else{
                total += sum
                sum = 0
            }
        }
        total += sum
    }
    return total
}
var result = 0
func dfs(_ x: Int, _ y: Int){
    if x == n {
        result = max(result, sum())
        return
    }
    
    if y == m{
        dfs(x + 1, 0)
        return
    }
//    print("x : \(x), y: \(y)")
    visited[x][y] = true
    dfs(x, y + 1)
    
    visited[x][y] = false
    dfs(x, y + 1)
}
dfs(0, 0)
print(result)