[Algorithm] Swift 백준 1018번

 

 

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

1018번: 체스판 다시 칠하기

 

문제접근 

문제를 정해진 시간까지 풀지 못했다. 사실.. 문제를 정확하게 이해하지 못한 게 큰 거 같다. 다른 풀이를 참고해서 문제를 풀었지만 풀이를 완전히 이해하는데 시간이 좀 걸렸다. 

 

정답풀이 

 

import Foundation

let input = readLine()!.split(separator: " ").map { Int($0)! }
let m = input[0], n = input[1]
var board: [[Character]] = []

for _ in 0..<m {
    board.append(readLine()!.map { $0 })
}

var answer = 64

for y in 0...m - 8 {
    for x in 0...n - 8 {
        
        var count1 = 0
        var count2 = 0
        
        for col in y..<y + 8 {
            for row in x..<x + 8 {
                if (col + row) % 2 == 0 {
                    if board[col][row] == "B" {
                        count2 += 1
                    } else {
                        count1 += 1
                    }
                } else {
                    if board[col][row] == "B" {
                        count1 += 1
                    } else {
                        count2 += 1
                    }
                }
            }
        }
        answer = min(answer, count2, count1)
    }
}

print(answer)

 

어떻게 방법으로 풀었는지 알아보자!  이해하는데 좀 걸린 만큼 자세하게 알아보자!! 

 

문제를 보면 우선 첫째 줄에 N M 이 주어진다고 한다. 

 

let input = readLine()!.split(separator: " ").map { Int($0)! } // [8, 8]

 

N, M을 우선 입력받아 준다.  split을 사용하면 공백단위로 값을 추출해서 배열로 변환시키게 된다. 

 

let n = input[0], m = input[1]

 

N, M을 저장해 준다. 

 

var board: [[Character]] = []

for _ in 0..<n {
    board.append(readLine()!.map { $0 })
}

 

보드를 저장할 수 있는 빈 배열을 생성해 주고 n 줄 까지 받아준다. 입력은 바로 보드 배열에 넣어준다. 

 

var answer = 64

 

여기서 위 코드를 작성하는 이유는 지민이가 보드에서 8x8 체스판을 잘라낸 후 다시 칠하기 때문에, 만약 모두 다시 칠해야 한다면 64번 이기 때문에 설정해 준 값이다.  

 

for y in 0...n - 8 {
    for x in 0...m - 8 {
        // 생략
    }
}

 

두 번의 반복문을 사용하는데 위 반복문 사용하는 이유는 

 

 

쉽게 예를 들어보자 N = 9, M = 9라는 크기의 보드가 들어온다면 N을 y축이라 두고 M을 축이라고 두자!!

그 후 지민이는 보드판에서 8x8 사이즈 크기의 체스판을 자르게 된다. 그러나 8x8 크기는 보드의 아무 곳에서나 골라서 잘라도 되기 때문에 9x9 사이즈 보드라면 4개의 선택지가 존재하는 것이다. 다시 코드를 보면 

 

for y in 0...n - 8 {
    for x in 0...m - 8 {
        // 생략
    }
}

 

n = 9, m = 9라면 

 

for y in 0...1 {
    for x in 0...1 {
        // 생략
    }
}

 

이렇게 되는데 (0,0), (0,1), (1,0), (1,1) 4번을 반복하게 된다. 결국 8x8 크기를 자를 수 있는 선택 개수를 정해주는 코드이다. 

 

var count1 = 0
var count2 = 0
        
for col in y..<y + 8 {
    for row in x..<x + 8 {
        if (col + row) % 2 == 0 {
            if board[col][row] == "B" {
                count2 += 1
            } else {
                count1 += 1
            }
        } else {
            if board[col][row] == "B" {
                count1 += 1
            } else {
                count2 += 1
            }
        }
    }
}
answer = min(answer, count2, count1)

 

내부 코드를 보자 ~ 

 

우선 count1, count2를 설정해 준다. 처음에 count1, count2가 어떤 걸 의미하는지 이해하는데 오래 걸렸다. 일단 코드를 다 보고 나면 이해할 수 있다. 

 

내부에 반복문이 또 사용되는데 요건 자른 8x8 크기의 체스판을 탐색하기 위한 반복문이다. 위에 예시를 가져오면 보드가 9x9일 때 

y =1, x =1 이면 

for col in 1..<9 {
    for row in 1..<9 {
        // 생략
    }
}

 

 

핑크박스 8x8에서 다시 칠해야 하는 개수를 찾고 있는 것이다. 

 

if (col + row) % 2 == 0 {
    if board[col][row] == "B" {
        count2 += 1
    } else {
        count1 += 1
    }
} else {
    if board[col][row] == "B" {
        count1 += 1
    } else {
        count2 += 1
    }
}

 

맨 왼쪽 위칸이 흰색인 체스판을 보면, 행과 열의 합이 짝수인 경우는 흰색으로, 홀수인 경우는 검은색으로 칠해져 있다. 맨 왼쪽 위칸이 검은색인 체스판은 행과 열의 합이 짝수인 경우는 검은색, 홀수인 경우는 흰색이다.

행과 열의 합이 짝수이고 흰색, 행과 열이 홀수이고 검은색인 체스판과 다른 개수와 행과 열의 합이 짝수이고 검은색, 행과 열이 홀수이고 흰색인 체스판과 다른 개수를 세어 더 적게 칠하는 경우를 계속해서 갱신해 주는 방식이다. 

 

 

이런 식으로 다시 칠해야 하는 정사각형을 찾게 된다. count1 은 WBWB 패턴일 때는 다시 칠 할 필요 없는 정사각형을 의미하고 count2는 다시 칠해야 하는 정사각형을 의미한다. BWBW 패턴은 반대로 생각하면 된다. 

 

answer = min(answer, count2, count1)

 

answer은 이전에 계산된 값보다 작은 값으로 계속 업데이트가 된다. 

 

위에서 answer = 64를 설정한 이유는 최대가 64번 색칠할 수 있고, 그 이상 높은 수가 나올 수 없기 때문에 min을 사용하기 위한 초기값이라고 생각하면 된다.

 

그러면 지민이가 다시 칠해야 하는 정사각형의 개수의 최솟값을 구할 수 있다. 

 

solved에서 CLASS 2 ++ 도전하고 있는데 첫 문제부터 만만치가 않았다. 느리더라도 하다 보면 되겠지 🔥

 

 

 

참고자료 

 

https://dev-mandos.tistory.com/141