체스판_다시_칠하기

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

오랜만에 풀어보는 알고리즘 문제였다. 어려운 문제는 아니고 손풀기 목적으로 골라본 문제였다. 처음 이 문제를 봤을 때 내가 접근했던 방식은 백트래킹을 생각했었다. 그리고 큐를 사용해서 후위표기식 느낌으로 모든 줄마다 push해서 pop했을 때 같은 색깔이 두 번 나오면 바꿔야되는 색을 하나씩 늘리는 것을 생각했다. 그런데 이렇게 할 경우 고려해야하는 예외의 경우가 너무 많아져서 포기했다. 후에 접근한 방식 문제를 다시 한번 잘 읽어보니, 체스판을 색칠하는 경우가 두 가지 뿐이라고 나와있었다. 즉, 내가 고려해야 하는 경우의 수는 두 개 뿐인 것이다. 좌상단이 검은색으로 시작하거나, 흰색으로 시작하거나이다. 이렇게 하면 모든 경우의 수를 다 고려할 수 있다. 보드를 나타내는 변수, n과 m을 나타내는 변수..