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

오랜만에 풀어보는 알고리즘 문제였다.

어려운 문제는 아니고 손풀기 목적으로 골라본 문제였다.

 

처음 이 문제를 봤을 때

내가 접근했던 방식은 백트래킹을 생각했었다.

그리고 큐를 사용해서 후위표기식 느낌으로 모든 줄마다

push해서 pop했을 때 같은 색깔이 두 번 나오면 바꿔야되는 색을 하나씩 늘리는 것을 생각했다.

그런데 이렇게 할 경우 고려해야하는 예외의 경우가 너무 많아져서 포기했다.

 

후에 접근한 방식

문제를 다시 한번 잘 읽어보니, 체스판을 색칠하는 경우가 두 가지 뿐이라고 나와있었다.

즉, 내가 고려해야 하는 경우의 수는 두 개 뿐인 것이다.

좌상단이 검은색으로 시작하거나, 흰색으로 시작하거나이다.

이렇게 하면 모든 경우의 수를 다 고려할 수 있다.

사용한 변수들과 메서드

보드를 나타내는 변수, n과 m을 나타내는 변수

그리고 결과값에 1^10의 값을 넣어놔서 첫번째 경우에는 무조건 갱신될 수 있도록 하였다.

그리고 leftTopBlack 메서드의 매개변수에는 가로 몇번째인지를 나타내는 i, 세로 j와

몇 번째 접근인지 나타내는 idx를 받았고 몇 개의 보드판이 바뀌어야 하는지를 나타내는 change_num 매개변수를 입력받았다.

메인함수

메인함수에서 보드를 입력받은 후에 보드를 만들 수 있는 index로 메서드를 접근했다.

change_num은 첫번째에는 다 0으로 받았다.

좌상단 흑, 백 메서드

좌상단 흑 백 메서드로 idx가 9번째일 때에는 result와 비교했을 때 어떤 값이 더 작은지 비교해서 변경해야 하는 값이 더 적다면 갱신될 수 있도록 삼항연산자를 이용해서 구현했다.

9번째가 안됐다면 내가 보고있는 세로번째를 기준으로 modulo 2를 했을 때 검은색인지 흰색인지 각 메서드에 맞게 접근하고 다음 줄에는 맨 첫번째가 반대가 되므로 반대 메서드를 호출하는 식으로 구현했다.

 

어려운 문제는 아니였다.

 

kimyunseok/study-record

코드 전문은 위에서 확인할 수 있다.