[프로그래머스 C#] Lv.3 / 2차원 동전 뒤집기

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

프로그래머스

1. 정답코드 및 핵심 아이디어, 유의사항

주어진 조건에 따라 초기 상태에서 목표 상태로 변경하기 위한 최소 변경 횟수를 구하는 문제

- 만약 목표 상태로 변경할 수 없다면 -1을 리턴

 

같은 행에 대한 연산이나 열에 대한 연산은 두번 이상 이루어져도 의미가 없음

 - 각 열과 행은 뒤집은 경우와 뒤집지 않은 경우로 나뉨

  -> DFS 알고리즘을 이용해 모든 경우의 수를 구함 (완전탐색)

https://godgjwnsgur7.tistory.com/47

[Algorithm C#] BFS, DFS ( + Back Tracking )

주석 참조

    using System;

    public class Solution
    {
        public int solution(int[,] beginning, int[,] target)
        {
            int answer = -1;

            // 각 인덱스에 대해 beginning == target ? 1 : -1 이 들어간 배열
            var intArrays = new int[target.GetLength(0), target.GetLength(1)];

            for (int i = 0; i < target.GetLength(0); i++)
                for (int j = 0; j < target.GetLength(1); j++)
                    intArrays[i, j] = (beginning[i, j] == target[i, j]) ? 1 : -1;

            DFS(0, 0, intArrays, ref answer);

            return answer;
        }

        public void DFS(int currNum, int count, int[,] intArrays, ref int answer)
        {
            int index = currNum;

            // 모든 행과 열에 대한 연산을 마쳤다면
            if (index == intArrays.GetLength(0) + intArrays.GetLength(1))
            {
                foreach (int num in intArrays)
                    if (num == -1)
                        return;

                // 목표상태에 도달한 경우라면
                if (answer == -1)
                    answer = count;
                else
                    answer = Math.Min(answer, count);

                return;
            }
            
            if (index >= intArrays.GetLength(0)) // 열 연산 (행 연산이 끝난 경우)
            {
                index -= intArrays.GetLength(0); // 인덱스 돌려놓기

                // 열을 뒤집은 경우
                for (int i = 0; i < intArrays.GetLength(0); i++)
                    intArrays[i, index] *= -1;

                DFS(currNum + 1, count + 1, intArrays, ref answer);

                for (int i = 0; i < intArrays.GetLength(0); i++)
                    intArrays[i, index] *= -1;

                // 뒤집지 않은 경우
                DFS(currNum + 1, count, intArrays, ref answer);
            }
            else // 행 연산
            {
                // 행을 뒤집은 경우
                for (int i = 0; i < intArrays.GetLength(1); i++)
                    intArrays[index, i] *= -1;

                DFS(currNum + 1, count + 1, intArrays, ref answer);

                for (int i = 0; i < intArrays.GetLength(1); i++)
                    intArrays[index, i] *= -1;

                // 뒤집지 않은 경우
                DFS(currNum + 1, count, intArrays, ref answer);
            }
        }
    }