백준 1018번 체스판 다시 칠하기

백준 1018번 체스판 다시 칠하기 문제이다.

문제는 다음과 같다. M*N의 색깔이 칠해진 판이 주어지고 해당 판에서 8*8의 구간을 골라 체스판을 만드는데

체스판은 흰색과 검정색이 번갈아 나오는 체스판을 만들어야 한다.

가장 적게 칠해서 체스판을 만드는 경우 몇번만 칠하면 되는지를 구하는 문제이다.

브루트포스 유형의 문제이기 때문에 하나하나 확인해 보도록 한다.

체스판은 8*8의 크기이고 해당 크기로 주어진 판에서 자를 수 있는 모든 경우를 확인해보자

언어는 ruby를 사용하여 프로그래밍 하였다.

def find1(arr, m, n)
    result = 64
    for i in 0...m-7
        for j in 0...n-7
            count = 0
            for k in 0...8
                a = k % 2
                for l in 0...8
                    if a % 2 == 0 && arr[k+i][l+j] == 'B'
                        count += 1
                    end
                    if a % 2 == 1 && arr[k+i][l+j] == 'W'
                        count += 1
                    end
                    a += 1  
                end
            end
            if count < result
                result = count
            end
        end
    end
    return result
end
def find2(arr, m, n)
    result = 64
    for i in 0...m-7
        for j in 0...n-7
            count = 0
            for k in 0...8
                a = k % 2
                for l in 0...8
                    if a % 2 == 0 && arr[k+i][l+j] == 'W'
                        count += 1
                    end
                    if a % 2 == 1 && arr[k+i][l+j] == 'B'
                        count += 1
                    end
                    a += 1  
                end
            end
            if count < result
                result = count
            end
        end
    end
    return result
end






m, n = gets().chomp().split()
m = m.to_i
n = n.to_i
arr = Array.new
for i in 0...m
    tmp = gets().chomp()
    arr.push(tmp.split(//))
end

result1 = find1(arr, m, n)
result2 = find2(arr, m, n)
if result1 < result2
    puts result1
else
    puts result2
end

 

예를 들어 9*9의 판이 주어진다면 8*8의 크기로 자르면 총 네가지의 경우가 나오게 된다.  

모든 경우를 각각 확인하는데 하나의 경우에서 두가지를 확인해주어야 한다.

체스판은 흰색으로 시작할 수도 있고 검은색으로 시작할 수도 있기 때문에

find함수를 1, 2로 만들어 두가지 경우를 모두 확인 하도록 하였다.

틀리지 않고 한번에 성공항였다.