ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [KOITP] 재밌는 게임(Not Solved)
    자료구조 및 알고리즘/문제풀이 2016. 12. 19. 09:33

    출처 : http://koitp.org/problem/SDS_PRO_1_8/read/


    시간 제한메모리 제한제출 횟수정답 횟수 (비율)정답자 수
    2.0 초512 MB980184 (19%)129
    문제

    형석이는 M*N 그리드 위에 놓여있는 MN개의 흰색과 검은색 돌들을 가지고 게임을 한다.

    image1

    인접해 있는 같은 색의 돌들은 같은 그룹을 형성한다. 위를 보면 A~F의 6개의 그룹을 확인할 수 있다. 여기서 하나의 그룹을 뒤집게 되면, 그 그룹의 색이 반전된다. 아래의 사진은 A그룹을 뒤집었을 때의 그림이다. A라는 그룹을 뒤집었을 때, 인접한 다른 색의 그룹과 합쳐지는 것을 확인할 수 있다. (흰색 B그룹과 합쳐졌다.)

    image1

    그 후, C를 뒤집게 되면, 아래와 같다. (마찬가지로, A,B,C,D가 한그룹이 되었다.)

    image1

    그 다음 위에 있는 흰색그룹을 뒤집으면, 전체가 검은색으로 바뀐다. 이렇게 전체를 모두 같은 색으로 만드는 것이 목표이다.

    문제는 위의 방법대로 진행하였을 때, 모든 바둑돌을 같은 색으로 만드는 최소한의 단계수를 구하는 것이다.

    시간제한: 1초

    입력

    첫째 줄에는 M*N 그리드는 나타내는 두 양의 정수 M과 N이 빈칸을 사이에 두고 주어진다. M과 N은 2이상 100이하이다. 둘째 줄부터 M개의 각 줄에는 그리드의 가로줄 한 줄에 놓여진 흰색 동을 나타내는 0과 검은색 돌을 나타내는 1이 빈칸을 사이에 두고 연속해서 N개가 주어진다.

    출력

    첫째 줄에 모든 돌들이 같은 색이 되도록 하는 색 바꾸기의 최소 횟수를 출력한다.

    힌트

    입력 예제

    5 6
    1 1 0 1 0 0
    1 0 0 1 1 1
    1 1 0 1 1 1
    0 0 0 0 0 0
    1 1 1 0 1 1
    

    출력 예제

    2


    댓글

Designed by Tistory.