23.07.14 파이썬 코딩 퀴즈#266 2차원 동전 뒤집기 (프로그래머스 스쿨)

이번 문제는 동전 뒤집기 문제이다.

전달받은 2차원 배열 beginning을 목표 배열인 target으로 만드는 최소한의 방법을 찾는 문제이며, 만약 목표 상태를 만들지 못할 경우에는 -1을 return 해야 한다.

특별한 제한 사항은 없다.

 

먼저 문제에 접근하는 방법을 생각해 보아야 한다.

target 에 맞추기 위해 그 기준을 어디에다가 둘 것인가?

앞서 풀었던 고고학 최고의 발견 문제와 비슷하다는 느낌이 든다.

입출력 예제 1번을 거꾸로 실행해 보았다. 역시 어느것을 먼저 실행 하여도 똑같이 5번에 똑같이 target으로 만드는게 가능하다. 즉 기준이 되는 행,열을 찾아 그 행,열을 기준으로 뒤집기를 시행하면 된다는 의미이다.

 

해당 문제를 풀기 위해서는 먼저 값이 다른 열을 기준으로 행과 열 중 무얼 뒤집을지 고민을 해보아야 한다.

위 그림과 같이 첫행과 첫열이 다른 두 배열이 존재한다.

이중 반복문으로 두 배열을 탐색하면 [0][1] 에서 제일 먼저 다른값이 나타난다.

이 때, [0]행을 뒤집을 것인가, [1] 열을 뒤집을 것인지 선택해야 한다. 아니 굳이 선택할 필요없이 두 경우를 상정해서 생각해 보아야 한다.

또한 첫열을 기준으로도 첫열을 뒤집을지, 아니면 값이 다른 행만 뒤집을지도 따져봐야 한다.

그리고 이렇게 뒤집어진 배열을 열을 우선 뒤집고 행을 뒤집는 경우와, 행을 우선 뒤집고 열을 뒤집는 경우도 생각해야 한다. 

 

코드를 작성해보자.

우선 첫열과 첫행을 기준으로 값이 다른 열과 행을 뒤집은 배열을 q에 넣어준다.

그리고 temp 에는 새롭게 뒤집힌 배열들을 넣어주어 while문이 끝나는 조건을 만들어 주면 된다.

즉 하나의 board를 기준으로 행을 우선 뒤집은 배열 board1과 열을 우선 뒤집은 배열 board2 를 만들어 주는 방법이다.

board를 뒤집는 함수는 굉장히 단순하기 때문에 따로 남겨두지 않아도 될 것 같다.