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

브루스 포스

브루트 포스(brute force), 키 전수조사(exhaustive key search) 또는 무차별 대입(無差別代入)이라 불리는 알고리즘있습니다, 알고리즘이라고 칭하기도 애매하지만 알고리즘입니다.

 

바로 모든 경우의 수를 때려 박는 알고리즘입니다.

 

가장 완벽하며 가장 비효율적인 알고리즘이라고 할 수 있습니다

브루스 포스로 문제를 하나 풀었습니다.

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

1018번: 체스판 다시 칠하기

 

처음에 흰색으로 시작할 때와 검은색으로 시작할 때를 두 개를 두고 비교해서 적은 쪽으로 계산해야 하다는

가정이 빠져 좀 헤매다가 검은색 시작의 경우의 수와 흰색 시작의 경우의 수를 넣음으로써 해결했습니다.

 

문제를 풀며 재미있었던 부분은 아래처럼 배열로 W, B를 구분하는 변수를  선언하고 

var stone = [2]byte{'W', 'B'}

아래 조건문처럼 돌의 색깔을  나누기 연산으로 현재의 돌 색을 정하는 코드입니다.  

처음 코드는 시작이 W가 나오고 뒤는 시작이 B로 시작하는 게 문제에 아주 적합했습니다.

if board[c][r] != stone[(c+r)%2] {
	way1++
}

if board[c][r] != stone[(c+r+1)%2] {
	way2++
}

 

전체 코드

전체 코드는 아래와 같습니다.

package main

import (
	"bufio"
	"fmt"
	"os"
	"slices"
)

func main() {
	var reader = bufio.NewReader(os.Stdin)
	var n, m int
	var size = 8

	fmt.Fscan(reader, &n)
	fmt.Fscanln(reader, &m)
	var board []string

	for i := 0; i < n; i++ {
		var str string
		fmt.Fscanln(reader, &str)
		board = append(board, str)
	}
	// 최악의 경우의 수로도 넘을 수 없는 값
	var min = n * m

	// 크기가 8이므로 8*8 체스판을 만들 수 있는 범위까지만 반복
	for i := 0; i <= n-size; i++ {
		for j := 0; j <= m-size; j++ {
			var stone = [2]byte{'W', 'B'}

			// way1: W로 시작하는 체스판
			way1 := 0
			for c := i; c < i+size; c++ {
				for r := j; r < j+size; r++ {
					if board[c][r] != stone[(c+r)%2] {
						way1++
					}
				}
			}

			// way2: B로 시작하는 체스판
			way2 := 0
			for c := i; c < i+size; c++ {
				for r := j; r < j+size; r++ {
					if board[c][r] != stone[(c+r+1)%2] {
						way2++
					}
				}
			}

			// 가장 작은 값 선택
			var results = []int{min, way1, way2}
			min = slices.Min(results)
		}
	}
	fmt.Println(min)
}