<Lv.3> 2차원 동전 뒤집기 (프로그래머스 : C#)

https://school.programmers.co.kr/learn/courses/30/lessons/131703

📕 문제 설명

동전들 초기 상태와 목표 상태 주어질 때 최소 뒤집어야 할 횟수 구하기

동전은 같은 줄의 모든 동전을 뒤집어야 함

• Input
  동전 초기 상태, 목표 상태
• Output
  초기 상태에서 목표 상태로 만들기 위해 필요한 동전 뒤집기의 최소 횟수 (목표 상태 불가능하면 -1 반환)

예제

풀이

예제 그림과 같이 행을 뒤집거나 뒤집지 않는 상황에서 열을 확인해보는 방식으로 풀었다. (이 경우 열이 하나라도 만족 안되면 바로 다음 케이스를 보기 때문에 완전 탐색할 필요가 없어진다.)
target을 만들 수 있는 경우 answer을 갱신해주었으며 flipcount는 뒤집어야할때 하나씩 추가해주는 식이다.

using System;

public class Solution {
    int r;
    int c;
    int[,] target;
    int[,] board;
    int answer = Int32.MaxValue;
    
    public int solution(int[,] beginning, int[,] targetBoard) {
        board = beginning;
        target = targetBoard;
        r = beginning.GetLength(0);
        c = beginning.GetLength(1);
        
        DFS(0,0);
        
        answer = answer == Int32.MaxValue ? -1 : answer;
        return answer;
    }
    
    public void DFS(int currentRow, int flipCount)
    {
        if (currentRow == r) // 마지막 행
        {
            for (int i = 0; i < c; i++)
            {
                int columnStatus = GetColumnStatus(i); // 현재 열 상태 확인
                if (columnStatus == -1) return; // 불가능 => pass
                flipCount += columnStatus; // 전부 반대면 + 1 (column 뒤집어야 하므로)
            }
            
            answer = Math.Min(answer, flipCount);
            return;
        }
        
        FlipRow(currentRow); // 행 뒤집기
        DFS(currentRow + 1, flipCount + 1); // 행 뒤집는 경우 (flip count 세주기)
        FlipRow(currentRow); // 원상 복구
        DFS(currentRow + 1, flipCount); //행 뒤집지 X
    }
    
    // 행 뒤집기
    public void FlipRow(int currentRow)
    {
        for (int i = 0; i < c; i++)
        {
            board[currentRow, i] = board[currentRow, i] == 0 ? 1 : 0;
        }
    }
    
    // 열 상태 확인
    public int GetColumnStatus(int currentColumn)
    {
        int status = -1; // 0: 뒤집기 x, 1: 뒤집기, -1: target 만들기 불가능한 케이스
        int flippedCount = 0;
        for (int i = 0; i < r; i++)
        {
            if (board[i, currentColumn] != target[i, currentColumn]) flippedCount += 1;
        }
        
        if (flippedCount == r) status = 1;
        else if (flippedCount == 0) status = 0;
        
        return status;
    }
}

결과