๐ฃ ๋ฌธ์ ์ดํด
1. ์ ๋ ฅ๋ฐ์ ์ฒด์คํ์ 8*8 ์ด์์ ํฌ๊ธฐ๋ฅผ ๊ฐ์ง๋ค.
2. ๋งจ ์ผ์ชฝ ์ ์นธ์ด ํฐ์์ธ ๊ฒฝ์ฐ, ํ๋๋ ๊ฒ์์์ธ ๊ฒฝ์ฐ ๋ ์ข ๋ฅ์ ํ์ผ๋ก ๋ง๋ค๊ณ ์ ํ๋ค.
3. ๊ฐ ์นธ์ด ๊ฒ์์๊ณผ ํฐ์ ์ค ํ๋๋ก ์์น ๋์ด ์๊ณ , ๋ณ์ ๊ณต์ ํ๋ ๋ ๊ฐ์ ์ฌ๊ฐํ์ ๋ค๋ฅธ ์์ผ๋ก ์น ํด์ ธ ์์ด์ผ ํ๋ค.
4. 8*8 ํฌ๊ธฐ์ ์ฒด์คํ์ผ๋ก ์๋ผ๋ธ ํ์ ๋ช ๊ฐ์ ์ ์ฌ๊ฐํ์ ๋ค์ ์น ํ๋ ค๊ณ ํ๋ค. ์ด๋, 8*8 ํฌ๊ธฐ๋ ์ฒด์คํ ๋ด ์ด๋์๋ ๊ณ ๋ฅผ ์ ์๋ค.
5. ๋ค์ ์น ํด์ผ ํ๋ ์นธ์ ์ต์ ๊ฐ์๋ฅผ ์ฐพ์์ผ ํ๋ค.
์์ ํ์(Brute-force Search) ๋ฐฉ์์ ์ฌ์ฉํ๋ค.
๐ญ ํ์ด ๊ณผ์
๋จผ์ ํฐ์ ์นธ์ผ๋ก ์์ํ๋ 8*8 ์ฒด์คํ๊ณผ ๊ฒ์ ์ ์นธ์ผ๋ก ์์ํ๋ 8*8 ์ฒด์คํ์ string ๋ฐฐ์ด๋ก ๋ง๋ค์ด๋์๋ค.
์์ค์ฝ๋ ์งํ ๋ฐฉ์์ ๋ค์๊ณผ ๊ฐ๋ค.
์ ๋ ฅ๋ฐ์ ์ฒด์คํ ์ข์ธก ์๋จ์์ ํ ์นธ์ฉ ์ด๋ํ๋ฉฐ ์ขํ๋ฅผ compare ํจ์๋ก ๋๊ฒจ์ฃผ๋ฉด
compare ํจ์์์๋ ์ธ์๋ก ๋๊ฒจ๋ฐ์ ์ขํ๋ฅผ ์ข์ธก์๋จ์ผ๋ก ํ๋ ์ ๋ ฅ๋ฐ์ดํฐ 8*8๋ฐฐ์ด๊ณผ ๋ฏธ๋ฆฌ ๋ง๋ค์ด๋ ํฐ์ ์ฒด์คํ, ๊ฒ์ ์ ์ฒด์คํ๊ณผ ๋น๊ตํ์ฌ ๋ค๋ฅธ ๊ฐ์๋งํผ ๊ฐ๊ฐ ์นด์ดํธํ๋ค.(wCount, bCount)
๊ทธ๋ฆฌ๊ณ ๋ ์ค ๋ ์์ ๊ฐ์ ๋ฆฌํดํ๊ฒ ๋๋ค.
๋ค์ ๋ฉ์ธ ํจ์์์๋ ๊ธฐ์กด์ result ๊ฐ๊ณผ ๋๊ฒจ๋ฐ์ compareํจ์์ ๊ฒฐ๊ณผ๊ฐ ์ค ๋ ์์ ๊ฒ์ ์ ์ฅํ๊ณ ,
๋ค์ ์ขํ๋ฅผ ๋ค์ compare ํจ์๋ก ๋๊ฒจ์ค๋ค.
์์ฑ ์ธ์ด: C++
#include <iostream>
#include <algorithm>
using namespace std;
// ์
๋ ฅ ๊ฐ์ ์ฑ์ธ ๋ฐฐ์ด(์ฒด์คํ)
char map[60][60] = {0,};
// ๋งจ ์ข์ธก ์๋จ ์นธ์ ์์ด ํฐ์์ธ ๊ฒฝ์ฐ
string whiteMap[8] = {
{"WBWBWBWB"},
{"BWBWBWBW"},
{"WBWBWBWB"},
{"BWBWBWBW"},
{"WBWBWBWB"},
{"BWBWBWBW"},
{"WBWBWBWB"},
{"BWBWBWBW"},
};
// ๋งจ ์ข์ธก ์๋จ ์นธ์ ์์ด ๊ฒ์ ์์ธ ๊ฒฝ์ฐ
string blackMap[8] = {
{"BWBWBWBW"},
{"WBWBWBWB"},
{"BWBWBWBW"},
{"WBWBWBWB"},
{"BWBWBWBW"},
{"WBWBWBWB"},
{"BWBWBWBW"},
{"WBWBWBWB"}
};
// ๋ฏธ๋ฆฌ ๋ง๋ค์ด๋ ์ฒด์คํ๊ณผ ์
๋ ฅ ๋ฐ์ดํฐ๋ฅผ ๋น๊ตํด์
// ํฐ์นธ์ผ๋ก ์์ํ๋ ํ๊ณผ ๊ฒ์ ์นธ์ผ๋ก ์์ํ๋ ํ ๊ฐ๊ฐ ์์ ํด์ผํ๋ ์นธ ์๋ฅผ ๊ตฌํ๊ณ
// ๋ ์ค ๋ ์์ ์๋ฅผ ๋ฆฌํดํ๋ค.
int compare(int tRow, int tColumn){
int wCount = 0, bCount = 0;
for (int i = 0; i < 8; ++i) {
for (int j = 0; j < 8; ++j) {
// ํฐ์นธ์ผ๋ก ์์ํ๋ ์ฒด์คํ์ ๋ง๋ค๊ธฐ ์ํด ์์ ํด์ผํ๋ ์นธ ์
if(whiteMap[i][j] != map[tRow+i][tColumn+j]) wCount++;
// ๊ฒ์ ์นธ์ผ๋ก ์์ํ๋ ์ฒด์คํ์ ๋ง๋ค๊ธฐ ์ํด ์์ ํด์ผํ๋ ์นธ ์
if(blackMap[i][j] != map[tRow+i][tColumn+j]) bCount++;
}
}
// ๋น๊ตํ์ฌ ์ต์๊ฐ์ ๋ฆฌํดํ๋ค.
if(wCount <= bCount) return wCount;
else return bCount;
}
int main(){
int row, column, result = 99999999;
scanf(" %d %d", &row, &column);
// ์
๋ ฅ ๊ฐ์ ๋ฐ๋ผ ์ฒด์คํ ์ฑ์ฐ๊ธฐ
for (int i = 0; i < row; ++i) {
for (int j = 0; j < column; ++j) {
scanf(" %c", &map[i][j]);
}
}
for (int i = 0; i <= row-8; ++i) {
for (int j = 0; j <= column-8; ++j) {
// ๊ฐ์ฅ ์ต์์ธ ๊ฐ์ ์ฐพ์๋ธ๋ค.
result = min(compare(i, j), result);
}
}
cout << result << endl;
return 0;
}
๐ ๋ฐฐ์ด ์
๋ฌธ์ ๋ฅผ ์ฒ์ ๋ดค์ ๋, ๊ฐ์ฅ ๋จผ์ ๋ ์ค๋ฅธ ๋ฐฉ์์ด ์ด ๋ฐฉ๋ฒ์ด์๋ค.
๊ทผ๋ฐ ๋ค๋ฅธ ๋ฐฉ๋ฒ์ ์ฐพ์ผ๋ ค ํ๋ค๋ณด๋ ์๊พธ ์ค์๊ฐ ์๊ฒจ ๋ฌธ์ ํ์ด์ ๋๋ฌด ๋ง์ ์๊ฐ์ด ๊ฑธ๋ ธ๋ค...
๋ธ๋ฃจํธ ํฌ์ค ๋ฐฉ์์ผ๋ก ์ ๊ทผํ๊ฒ ๋ค๊ณ ํ๋จํ ๋งํผ,(์ฌ์ค ๋ฌธ์ ์ ํ ์์ฒด๊ฐ ๋ธ๋ฃจํธํฌ์ค๋ผ๊ณ ์ฐ์ฌ์๊ธด ํ์ง๋ง;;)
์ฐ์ ์ถฉ๋ถํ ํฉ๋ฆฌ์ ์ด๋ผ๊ณ ํ๋จ๋๋ฉด ๋ฐ๋ก ์งํํ๋ ์ต๊ด์ ๋ค์ฌ๋ด์ผ๊ฒ ๋ค.