(JAVA) 백준 1018번 : 체스판 다시 칠하기

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

1018번: 체스판 다시 칠하기

 

이건 좀

브루트 포스에 가까운

시뮬레이션 문제였습니다..

 

 

정공법으로

for문으로 탐색해도 메모리 크게 차지하지 않더군요.. 속도도 높지 않고.

 

 

 

 

메커니즘을 포스팅할거지만

 

다른 사람들 풀이 방법을 보니

 

꼭 제가 푸는 방법이 정답이 아닐 수 있어

 

 

제가 어떤식으로 이 문제를 풀었는지

 

핵심만 적겠습니다!

 

 

저는 우선

 

크게

 

1) W로 시작

2) B로 시작

(인덱스가 0 부터 n - 1 까지라고 가정했을 때 0, 0에 해당하는 값)

두 갈래로 나눠서

 

2차원 배열 boolean 2개를 만들었습니다.

*** 굳이 배열 만들지 않고 바로 for문 돌려서 비교해도 될 것 같군요..

 

 

해당 인덱스의 값이 'W' 인 경우

     짝수행 -> 짝수열 : B로 시작할 경우 B가 들어와야 하기 때문에 다시 칠해야 함. 따라서, 2) 배열의 같은 인덱스의 원소 값을 true로 변경.

     짝수행 -> 홀수열 : W로 시작할 경우 B가 들어와야 하기 때문에 다시 칠해야 함. 따라서, 1) 배열의 같은 인덱스의 원소 값을 true로 변경.

     홀수행 -> 짝수열 : W로 시작할 경우 B가 들어와야 하기 때문에 다시 칠해야 함. 따라서, 1) 배열의 같은 인덱스의 원소 값을 true로 변경.

     홀수행 -> 홀수열 : B로 시작할 경우 B가 들어와야 하기 때문에 다시 칠해야 함. 따라서, 2) 배열의 같은 인덱스의 원소 값을 true로 변경.

 

 

이런 공식으로 해당 인덱스의 값이 'B' 인 경우에도 처리를 해줍니다.

 

 

 

마지막으로, 8 x 8 배열 고정으로 다시 칠하는 최소 경우를 구해야 하기 때문에

 

8 x 8 배열 내 true인 값이 있으면 counting을 진행하고, 

 

이중 가장 최소인 값을 출력하면 끝!

*** for문 진행 시 y = 0; y <= 전체 y길이 - 8; y++ 2중 for문(x도 똑같이) 방식으로 진행해야 인덱스 초과 없이 전부 탐색 가능합니다.

 

 

 

 

 

감사합니다.

 

소스코드

---