문제
바이너리 스도쿠 게임은 스도쿠의 변형 게임이다. 스도쿠와 비슷하게, 9*9칸으로 이루어져 있고, 이 칸은 각각 3*3 크기의 작은 칸으로 나누어져 있다. 스도쿠와 다른 점은 바이너리 스도쿠에서는 오직 0과 1만 이용해서 스도쿠 퍼즐을 푼다는 점이다.
000 000 000
001 000 100
000 000 000
000 110 000
000 111 000
000 000 000
000 000 000
000 000 000
000 000 000
바이너리 스도쿠의 목표는 최대한 적은 비트를 토글시켜서 각각의 행과 열, 그리고 3*3크기의 구간에 포함된 1의 개수가 짝수개가 되게 하는 것이다.
위의 예제는 3번 만에 퍼즐을 풀 수 있다.
000 000 000
001 000 100
001 000 100
000 110 000
000 110 000
000 000 000
000 000 000
000 000 000
000 000 000
바이너리 스도쿠 퍼즐의 초기 상태가 주어졌을 때, 이 퍼즐을 풀기 위해 필요한 최소 토글의 수를 구하는 프로그램을 작성하시오.
출력
바이너리 스도쿠를 풀기 위해 필요한 최소 토글의 수를 출력한다.
힌트
토글이란 0->1, 1->0으로 바꾸는 연산이다.
W3sicHJvYmxlbV9pZCI6IjU5MjMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjMTRcdWM3NzRcdWIxMDhcdWI5YWMgXHVjMmE0XHViM2M0XHVjZmUwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWJjMTRcdWM3NzRcdWIxMDhcdWI5YWMgXHVjMmE0XHViM2M0XHVjZmUwIFx1YWM4Y1x1Yzc4NFx1Yzc0MCBcdWMyYTRcdWIzYzRcdWNmZTBcdWM3NTggXHViY2MwXHVkNjE1IFx1YWM4Y1x1Yzc4NFx1Yzc3NFx1YjJlNC4gXHVjMmE0XHViM2M0XHVjZmUwXHVjNjQwIFx1YmU0NFx1YzJiN1x1ZDU1OFx1YWM4YywgOSo5XHVjZTc4XHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAsIFx1Yzc3NCBcdWNlNzhcdWM3NDAgXHVhYzAxXHVhYzAxIDMqMyBcdWQwNmNcdWFlMzBcdWM3NTggXHVjNzkxXHVjNzQwIFx1Y2U3OFx1YzczY1x1Yjg1YyBcdWIwOThcdWIyMDRcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWMyYTRcdWIzYzRcdWNmZTBcdWM2NDAgXHViMmU0XHViOTc4IFx1YzgxMFx1Yzc0MCBcdWJjMTRcdWM3NzRcdWIxMDhcdWI5YWMgXHVjMmE0XHViM2M0XHVjZmUwXHVjNWQwXHVjMTFjXHViMjk0IFx1YzYyNFx1YzljMSAwXHVhY2ZjIDFcdWI5Y2MgXHVjNzc0XHVjNmE5XHVkNTc0XHVjMTFjIFx1YzJhNFx1YjNjNFx1Y2ZlMCBcdWQzN2NcdWM5OTBcdWM3NDQgXHVkNDdjXHViMmU0XHViMjk0IFx1YzgxMFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHByZT5cclxuMDAwIDAwMCAwMDBcclxuMDAxIDAwMCAxMDBcclxuMDAwIDAwMCAwMDBcclxuXHJcbjAwMCAxMTAgMDAwXHJcbjAwMCAxMTEgMDAwXHJcbjAwMCAwMDAgMDAwXHJcblxyXG4wMDAgMDAwIDAwMFxyXG4wMDAgMDAwIDAwMFxyXG4wMDAgMDAwIDAwMDxcL3ByZT5cclxuXHJcbjxwPlx1YmMxNFx1Yzc3NFx1YjEwOFx1YjlhYyBcdWMyYTRcdWIzYzRcdWNmZTBcdWM3NTggXHViYWE5XHVkNDVjXHViMjk0IFx1Y2Q1Y1x1YjMwMFx1ZDU1YyBcdWM4MDFcdWM3NDAgXHViZTQ0XHVkMmI4XHViOTdjIFx1ZDFhMFx1YWUwMFx1YzJkY1x1Y2YxY1x1YzExYyBcdWFjMDFcdWFjMDFcdWM3NTggXHVkNTg5XHVhY2ZjIFx1YzVmNCwgXHVhZGY4XHViOWFjXHVhY2UwIDMqM1x1ZDA2Y1x1YWUzMFx1Yzc1OCBcdWFkNmNcdWFjMDRcdWM1ZDAgXHVkM2VjXHVkNTY4XHViNDFjIDFcdWM3NTggXHVhYzFjXHVjMjE4XHVhYzAwIFx1YzlkZFx1YzIxOFx1YWMxY1x1YWMwMCBcdWI0MThcdWFjOGMgXHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzA0XHVjNzU4IFx1YzYwOFx1YzgxY1x1YjI5NCAzXHViYzg4IFx1YjljY1x1YzVkMCBcdWQzN2NcdWM5OTBcdWM3NDQgXHVkNDgwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwcmU+XHJcbjAwMCAwMDAgMDAwXHJcbjAwMSAwMDAgMTAwXHJcbjAwMSAwMDAgMTAwXHJcblxyXG4wMDAgMTEwIDAwMFxyXG4wMDAgMTEwIDAwMFxyXG4wMDAgMDAwIDAwMFxyXG5cclxuMDAwIDAwMCAwMDBcclxuMDAwIDAwMCAwMDBcclxuMDAwIDAwMCAwMDA8XC9wcmU+XHJcblxyXG48cD5cdWJjMTRcdWM3NzRcdWIxMDhcdWI5YWMgXHVjMmE0XHViM2M0XHVjZmUwIFx1ZDM3Y1x1Yzk5MFx1Yzc1OCBcdWNkMDhcdWFlMzAgXHVjMGMxXHVkMGRjXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1Yzc3NCBcdWQzN2NcdWM5OTBcdWM3NDQgXHVkNDgwXHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjZDVjXHVjMThjIFx1ZDFhMFx1YWUwMFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIFx1YzU0NFx1ZDY0OSBcdWJjODhcdWM5ZjggXHVjOTA0IFx1YWU0Y1x1YzljMCBcdWJjMTRcdWM3NzRcdWIxMDhcdWI5YWMgXHVjMmE0XHViM2M0XHVjZmUwXHVjNzU4IFx1Y2QwOFx1YWUzMCBcdWMwYzFcdWQwZGNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YmMxNFx1Yzc3NFx1YjEwOFx1YjlhYyBcdWMyYTRcdWIzYzRcdWNmZTBcdWI5N2MgXHVkNDgwXHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjZDVjXHVjMThjIFx1ZDFhMFx1YWUwMFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWQxYTBcdWFlMDBcdWM3NzRcdWI3ODAgMC0mZ3Q7MSwgMS0mZ3Q7MFx1YzczY1x1Yjg1YyBcdWJjMTRcdWFmYjhcdWIyOTQgXHVjNWYwXHVjMGIwXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiNTkyMyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkJpbmFyeSBTdWRva3UiLCJkZXNjcmlwdGlvbiI6IjxwPkZhcm1lciBKb2huJiMzOTtzIGNvd3MgbGlrZSB0byBwbGF5IGFuIGludGVyZXN0aW5nIHZhcmlhbnQgb2YgdGhlIHBvcHVsYXIgZ2FtZSBvZiAmcXVvdDtTdWRva3UmcXVvdDsuICZuYnNwO1RoZWlyIHZlcnNpb24gaW52b2x2ZXMgYSA5IHggOSBncmlkIG9mIDMgeCAzIHN1YmdyaWRzLCBqdXN0IGxpa2UgcmVndWxhciBTdWRva3UuICZuYnNwO1RoZSBjb3dzJiMzOTsgdmVyc2lvbiwgaG93ZXZlciwgdXNlcyBvbmx5IGJpbmFyeSBkaWdpdHM6PFwvcD5cclxuXHJcbjxwcmU+XHJcbjAwMCAwMDAgMDAwXHJcbjAwMSAwMDAgMTAwXHJcbjAwMCAwMDAgMDAwXHJcblxyXG4wMDAgMTEwIDAwMFxyXG4wMDAgMTExIDAwMFxyXG4wMDAgMDAwIDAwMFxyXG5cclxuMDAwIDAwMCAwMDBcclxuMDAwIDAwMCAwMDBcclxuMDAwIDAwMCAwMDBcclxuPFwvcHJlPlxyXG5cclxuPHA+VGhlIGdvYWwgb2YgYmluYXJ5IFN1ZG9rdSBpcyB0byB0b2dnbGUgYXMgZmV3IGJpdHMgYXMgcG9zc2libGUgc28gdGhhdCBlYWNoIG9mIHRoZSBuaW5lIHJvd3MsIGVhY2ggb2YgdGhlIG5pbmUgY29sdW1ucywgYW5kIGVhY2ggb2YgdGhlIG5pbmUgMyB4IDMgc3ViZ3JpZHMgaGFzIGV2ZW4gcGFyaXR5IChpLmUuLCBjb250YWlucyBhbiBldmVuIG51bWJlciBvZiAxcykuICZuYnNwO0ZvciB0aGUgZXhhbXBsZSBhYm92ZSwgYSBzZXQgb2YgMyB0b2dnbGVzIGdpdmVzIGEgdmFsaWQgc29sdXRpb246PFwvcD5cclxuXHJcbjxwcmU+XHJcbjAwMCAwMDAgMDAwXHJcbjAwMSAwMDAgMTAwXHJcbjAwMSAwMDAgMTAwXHJcblxyXG4wMDAgMTEwIDAwMFxyXG4wMDAgMTEwIDAwMFxyXG4wMDAgMDAwIDAwMFxyXG5cclxuMDAwIDAwMCAwMDBcclxuMDAwIDAwMCAwMDBcclxuMDAwIDAwMCAwMDBcclxuPFwvcHJlPlxyXG5cclxuPHA+R2l2ZW4gdGhlIGluaXRpYWwgc3RhdGUgb2YgYSBiaW5hcnkgU3Vkb2t1IGJvYXJkLCBwbGVhc2UgaGVscCB0aGUgY293cyBkZXRlcm1pbmUgdGhlIG1pbmltdW0gbnVtYmVyIG9mIHRvZ2dsZXMgcmVxdWlyZWQgdG8gc29sdmUgaXQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD4qIExpbmVzIDEuLjk6IEVhY2ggbGluZSBjb250YWlucyBhIDktZGlnaXQgYmluYXJ5IHN0cmluZyBjb3JyZXNwb25kaW5nIHRvIG9uZSByb3cgb2YgdGhlIGluaXRpYWwgZ2FtZSBib2FyZC48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+KiBMaW5lIDE6IFRoZSBtaW5pbXVtIG51bWJlciBvZiB0b2dnbGVzIHJlcXVpcmVkIHRvIG1ha2UgZXZlcnkgcm93LCBjb2x1bW4sIGFuZCBzdWJncmlkIGhhdmUgZXZlbiBwYXJpdHkuPFwvcD5cclxuIiwiaGludCI6IjxwPlRocmVlIHRvZ2dsZXMgc3VmZmljZSB0byBzb2x2ZSB0aGUgcHV6emxlLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=