[Swift][구현] 백준 16931번 (겉넓이 구하기)

요구능력

구현, 수학

 

문제풀이

겉넓이만 구하면 되겠다고 생각하면 안된다.

울퉁불퉁(?)하기 때문에 옆에서 보는모습이 전부가 아니다.

이렇게 앞에서 봤을 때 빨간색으로 칠한부분이 옆에서는 안보인다.

이걸 어떻게 해결해야할까?

결론부터 말하자면,

N*M의 겉을 0으로 둘러싸고 N*M을 4방향탐색해주면서 겉넓이를 구하면 된다.

이 배열이 저장되어있는 arr이라는 배열이 있다.

그럼, arr[1][1]부터 탐색을 시작하는거다.

빨간동그라미 부분의 4방향을 탐색해보자.

왼쪽 0, 위 0, 오른쪽 3, 아래 2이다.

인접한부분의 값이 자기자신보다 작으면 겉넓이를 더해준다.

직접 해보면 이해가 가겠지만

왼쪽 0이라서 1이더크니까 겉넓이가 1이 더해질것이다.

그럼 이 겉넓이는 왼쪽면에서 더해지는 겉넓이라고 생각하면 된다.

4방향이라고 쪼개서 생각하지말고, 아래그림에서 화살표방향이 왼쪽면에서 바라본 방향이다.

이대로만 보면 왼쪽방향에서 바라본 겉넓이는 4 + 3 + 4 인 11이 나온다.

우리가 생각하고 있던 왼쪽면의 넓이가 나오는 것이다.

그래서 4방향 탐색을 하는것이고 자기보다 작은수가 나왔을 때 겉넓이를 더해주는데, 겉을 0으로 둘러쌓아야만 맨아래부터 더해주게되니까 0으로 둘러쌓아주는것이다.

 

후기

처음에는 이해안되서 못풀고 다른분들꺼 봐도 이해안되다가 직접 탐색해보다가 이해했는데

왠만한 골드 구현문제보다는 어려운거같고 겉넓이풀이가 이렇게도 되는구나 싶다..

혼자서 푸신분들 Respect..

 

코드

let dx = [-1, 1, 0, 0]
let dy = [0, 0, -1, 1]

let nm = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = nm[0]
let m = nm[1]

var arr = Array(repeating: Array(repeating: 0, count: 102), count: 102)
for i in 1...n{
    let a = readLine()!.split(separator: " ").map{Int(String($0))!}
    for j in 1...m{
        arr[i][j] = a[j - 1]
    }
}
var result = 0
for i in 1...n{
    for j in 1...m{
        
        for k in 0..<4{
            let nx = i + dx[k]
            let ny = j + dy[k]
            
            if arr[i][j] >= arr[nx][ny]{
                result += arr[i][j] - arr[nx][ny]
            }
        }
    }
}
result += 2 * n * m
print(result)