백준 1018번 문제를 처음 봤을 때
단순히 8×8 체스판을 잘라서 색을 비교하면 되는 문제라고 생각했다.
하지만 막상 구현하려고 하니, 어떤 기준으로 비교해야 하는지 모르겠어서 이부분에서 막혔다.
이 문제는 단순 구현 문제가 아니었다
이 문제의 핵심은
“체스판을 다시 칠하라”가 아니라,
“정답이 될 수 있는 기준이 여러 개일 수 있다”
는 점이었다.
정상적인 체스판은 사실 두 가지가 있다.
- 왼쪽 위가 W로 시작하는 체스판
- 왼쪽 위가 B로 시작하는 체스판
문제에서는 어느 쪽이 정답이라고 정해주지 않았기 때문에,
두 기준을 모두 계산한 뒤 최소값을 선택해야 한다.
왜 W 기준과 B 기준의 결과가 달라질까?
같은 8×8 체스판이라도
어떤 색을 시작점으로 두느냐에 따라
“틀린 칸”의 개수가 달라질 수 있다.
즉,
- W 기준에서는 많이 고쳐야 하지만
- B 기준에서는 적게 고쳐도 되는 경우가 존재한다.
그래서 한 기준만 보고 답을 정하면
틀릴 수 있다.
두가지 케이스 모두 고려하여 답을 적어야하므로, 조건을 나눠야한다.
(x + y) % 2 로 색을 판단하는 이유
체스판에는 아주 중요한 규칙이 있다.
한 칸 이동할 때마다 색이 바뀐다
이를 좌표로 표현하면 다음과 같다.
- (0,0)에서 시작해
- 아래로 x번, 오른쪽으로 y번 이동하면
- 총 이동 횟수는 x + y
이 값이
- 짝수면 시작 색
- 홀수면 반대 색
이 된다.
그래서 (x + y) % 2 를 기준으로
각 칸에 와야 할 색을 판단할 수 있다.
전체 풀이 흐름 정리
이 문제의 전체적인 접근 방식은 다음과 같다.
- 가능한 모든 8×8 시작 위치를 탐색한다
- 각 8×8 영역에 대해
- W로 시작하는 경우
- B로 시작하는 경우
를 각각 계산 해야한다.
- 두 경우 중 더 작은 값을 선택한다
- 모든 경우 중 최소값을 정답으로 갱신한다
이 문제를 통해 배운 점
이 문제를 풀면서 느낀 가장 큰 교훈은 다음이다.
기준이 여러 개일 수 있는 문제에서는
하나를 선택하지 말고,
모두 계산해서 비교해야 한다.
단순히 구현이 어려웠던 문제가 아니라,
사고 방식을 한 단계 확장해주는 문제였다고 느꼈다.
구현 코드는 깃허브에 정리해두었다.
이 글에서는 코드보다 사고 과정 위주로 정리했다.
https://github.com/yeji-dev25/algorithm-practice/blob/main/src/backjun/silver/brute_force/B1018.java