[백준 알고리즘] 1018번 : 체스판 다시 칠하기, c++

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

1018번: 체스판 다시 칠하기

c++로 백준 1018번 문제를 풀어보겠다.

 

 

 

 

 

문제

지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다.

체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.

보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8×8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8*8 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.

출력

첫째 줄에 지민이가 다시 칠해야 하는 정사각형 개수의 최솟값을 출력한다.

예제 입력 1 복사

8 8
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBBBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW

예제 출력 1 복사

1

 

 

 

 

 

<문제 풀이>

1. N, M을 선언한 후 입력받는다.

2. char형의 2차원 배열 char arr[N][M] 을 선언한 후 배열을 입력받아 저장한다.

3. 중첩 for문을 사용해 (N-7)*(M-7)번 (만들어 질 수 있는 8*8 체스판의 가짓수) 을 반복하며,

   그 안에 잘못 작성되어있는(새로 써야하는) char의 개수를 count한다.

   count하며 가장 작은 count는 출력해야 하기 때문에 따로 min에 기억해둔다.

4. 위의 중첩 for문에서 정해준 8*8체스판 부분을 또 다른 중첩 for문을 통해 잘못된 'B'와 'W'의 개수를 count한다.

5. min을 출력한다.

 

 

 

이 문제를 통해 알게된 점 : 

- (N-7)*(M-7) 번 반복해야 할 때, 나는 처음에 while 반복문을 사용했었는데 중첩 for문을 통해서도 가능하다는 것을 다시 깨달았다.

 

- 잘못된 'B'와 'W'를 판별하는 부분에서, 처음에 나는 앞에 있는 문자와 다음의 문자가 같으면 count하도록 했었는데 그러면 줄이 바뀌는 부분은 고려할 수 없었다.

그렇기 때문에 배열의 특성을 이용하여, 현재의 위치를 나타내는 i 와 j 를 사용했다.

(i + j) % 2 == 0 인 부분은 'B'가 와야 하고 (i + j) % 2 == 1 인 부분은 'W'가 와야 하므로 그게 아니라면 잘못 되어 있는 것이므로 count를 하도록 만들어 오류도 해결했고 코드도 더 간결해졌다.

 

- 중첩 for문(x, y) 안에 또 다른 중첩 for문(i, j)이 들어가있는 형태일 때, 

안에 들어간 중첩 for문(i, j)의 조건부 부분에 밖의 중첩 for문(x, y)의 조건부에서 사용했던 변수 x, y 를 사용하면 코드가 더 깔끔하고 복잡한 논리관계도 비교적 간단하게 해결된다는 것을 깨달았다. 

 

 

 

코드는 다음과 같다.