[Algorithm] Swift 백준 2563번

 

 

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

 

 

문제접근 

 

 

흰색 도화지는 가로, 세로의 크기가 100인 정사각형이고 

그 안에 가로, 세로 크기가 10인 정사각형 모양의 검은 색종이를 붙인다고 함.

 

 

여기서 가장 핵심은 사진에서 보이듯이 검은 색종이가 겹칠 수 도 있다는 점임!!

 

결과적으로 검은 색종이가 붙은 영역을 구해야 하는데 

 

만약 검은 색종이가 겹치지 않고 3개가 붙어있다면 100(한 장의 영역) X 3 해주면 300이 나옴

 

만약 이렇게 쉽다면 얼마나 좋을까.. 하지만 위 이미지와 같이 검은 색종이는 중복으로 붙여지는 구간이 있기 때문에 중복된 부분은 빼주어야 함!! 

 

 그래서 처음에는 예제 입력으로 주어지는 수를 이용해서 풀어보려고 했음.

 

그래서 우선 처음 들어오는 검은 색종이를 바탕으로 색종이가 차지하는 넓이 범위에 다음으로 오는 검은 색종이가 들어오면 범위를 계산해서 두 검은 색종이의 범위를 더한 200에서 중복된 넓이를 빼주려고 했음! 

 

하지만 100개나 들어올 수 있는 모든 검은 색종이의 범위를 일일이 계산해서 다음 색종이랑 범위 비교해서 겹치는 부분을 찾아내는 것은 말이 안 된다고 생각함!!.. 

 

그래서 배열을 이용해서 풀어야 하나??🤔 배열을 이용하면 중복을 쉽게 해결할 수 있겠는데!라고 생각이 들기 시작함.

 

0으로 가득 찬 100*100 배열을 만들어주고 검은 색종이 범위만큼 1로 변경해 주면 중복도 처리할 수 있고  

 

나중에 모든 검은 색종이 넓이를 찾기 위해서 배열에서 1만 count 해서 구하면 나올 거 같다는 생각을 함!! 

 

 

정답풀이

 

// 우선 0으로 가득찬 100 * 100 을 만들어줌
var whiteArr = Array(repeating: Array(repeating: 0, count: 101), count: 101)

 

 

// 검은색 색종이 부분을 1로 변경해주고 있음
for _ in 0..<count {
    let location = readLine()!.split(separator: " ").map { Int(String($0))!}
    let (x, y) = (location[0], location[1])
    for i in x...x+10 {
        for j in y...y+10 {
            whiteArr[i][j] = 1
        }
    }
}

 

위 코드는 검은색 색종이 부분을 배열에서 1로 만들어주고 있음 

 

만약 3 7 이 들어온다면 

 

가로, 세로 크기가 각각 10인 정사각형 이기 때문에 가로는 3~ 13까지 세로는 7~17까지 1로 바꾸어주면 됨!!

 

이렇게 바꿔주면 중복된 부분도 계속 1로 바뀌면서 유지됨!

 

모든 검은 색종이 개수만큼 반복 후 마지막으로 검은색 색종이의 넓이인 1의 개수를 구해주면 됨.

 

print(whiteArr.flatMap { $0 }.filter { $0 == 1 }.count)

 

여기서 flatMap이 무엇이냐~~ 

 

 

이 시퀀스의 각 요소와 함께 지정된 변환을 호출한 결과가 연결된 배열을 반환합니다.라고 함

 

let numbers = [1, 2, 3, 4]

let mapped = numbers.map { Array(repeating: $0, count: $0) }
// [[1], [2, 2], [3, 3, 3], [4, 4, 4, 4]]

let flatMapped = numbers.flatMap { Array(repeating: $0, count: $0) }
// [1, 2, 2, 3, 3, 3, 4, 4, 4, 4]

 

2차원 배열이 1차원 배열이 되어 평평한 배열(flattened array)을 리턴하고 있음.

 

100 * 100으로 만든 2차원 배열을 1차원 배열로 만들어준 뒤 1의 개수를 구해서 출력해주고 있음!!

 

이제 예시 입력을 넣어보자 

 

 

어!! 260이 나와야 하는데 왜?? 303이 나와?? 😱

 

다시 코드를 보자!!

// 검은색 색종이 부분을 1로 변경해주고 있음
for _ in 0..<count {
    let location = readLine()!.split(separator: " ").map { Int(String($0))!}
    let (x, y) = (location[0], location[1])
    for i in x...x+10 {
        for j in y...y+10 {
            whiteArr[i][j] = 1
        }
    }
}

 

반복문 부분을 다시 보면 x...x+10까지 반복을 하고 있는데 

 

그림으로 보는 가로의 크기는 3 ~ 13까지가 10이 맞지만 

배열로 보았을 때는 11개가 되는 것임 

 

그래서 x..<x+10까지 반복해주어야 했음!!

그래야지 3 ~ 12까지 10개가 되어서 크기가 10인걸 배열로 표현할 수 있음.

 

for _ in 0..<count {
    let location = readLine()!.split(separator: " ").map { Int(String($0))!}
    let (x, y) = (location[0], location[1])
    for i in x..<x+10 {
        for j in y..<y+10 {
            whiteArr[i][j] = 1
        }
    }
}

 

 

전체 코드 

 

import Foundation

var whiteArr = Array(repeating: Array(repeating: 0, count: 101), count: 101)

let count = Int(readLine()!)!

for _ in 0..<count {
    let location = readLine()!.split(separator: " ").map { Int(String($0))!}
    let (x, y) = (location[0], location[1])
    for i in x..<x+10 {
        for j in y..<y+10 {
            whiteArr[i][j] = 1
        }
    }
}

print(whiteArr.flatMap { $0 }.filter { $0 == 1 }.count)

 

 

항상 코테문제는 그래서 어떻게 접근할 건데?? 이게 중요한 거 같음!! 그래야지 문제를 풀 수 있으니깐.... 

 

더 다양한 문제를 풀어보면서 여러 가지 방식으로 문제를 바라볼 수 있도록 노력해야겠음!!!

 

 

 

참고 및 인용

 

https://developer.apple.com/documentation/swift/string/flatmap(_:)-i3m9