<Lv.3> 고고학 최고의 발견 (프로그래머스 : C#)

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

📕 문제 설명

퍼즐은 시계들이 행렬을 이루는 구조물로 하나의 식에 하나의 시곗 바늘이 존재한다.

시곗 바늘 => 시계 방향, 90도 돌리기 가능

하나의 시계를 돌릴 때 상하 좌우 인접한 시계들의 시곗 바늘도 같이 돌아간다. 각 시계는 12, 3, 6, 9시의 방향 중 한 방향을 가리키고 있다. 각 시계의 시곗바늘을 적절히 조작하여 모든 시곗 바늘이 12시 방향을 가리키면 퍼즐이 해결된다. 이때의 최소한의 횟수 반환하기

• Input
  시곗바늘 행렬
• Output
  최소한의 조작 횟수

예제

풀이

첫번째 행에 대해 모든 경우의 수가 정해지면 밑의 행들은 위의 행에 맞춰 자연스레 회전 수가 정해진다. 따라서, 첫번째 행의 모든 경우에 대해 밑의 행들을 확인하며 가능한 경우들에 대해 최소 회전 수를 구해나간다.

using System;

public class Solution {
    int N, answer = Int32.MaxValue;
    int[,] map;
    int[] rotationCount;
    int[] dx = {0,0,0,1,-1};
    int[] dy = {0,1,-1,0,0};
    
    public int solution(int[,] clockHands) {
        N = clockHands.GetLength(0);
        map = new int[N,N];
        rotationCount = new int[N];
        for (int i = 0; i < N; i++) 
        {
            for (int j = 0; j < N; j++)
            {
                map[i,j] = (4 - clockHands[i,j]) % 4; // 12시 만들기 위해 필요한 조작횟수 담기
            }
        }

        DFS(0);
        return answer;
    }

    // 첫번째 줄 0~N-1 번째 칼럼의 회전수 정하기
    public void DFS (int ind) {
        if (ind == N)
        {
            int[,] mapClone = (int[,])map.Clone();
            int[] rotationCountClone = (int[])rotationCount.Clone();

            int totalRotationCount = 0;
            for (int i = 0; i < N; i++) 
            {
                for (int j = 0; j < N; j++) 
                {
                    totalRotationCount += rotationCountClone[j];
                    // 4방향 + 현재 위치 시계 회전시키기
                    for (int d = 0; d < 5; d++) 
                    {
                        int newX = i + dx[d];
                        int newY = j + dy[d];
                        if (newX < 0 || newY < 0 || newX >= N || newY >= N) continue;
                        // 인접한 시계들 회전해주기
                        mapClone[newX,newY] = mapClone[newX,newY] - rotationCountClone[j] >= 0 ? mapClone[newX,newY] - rotationCountClone[j] : mapClone[newX,newY] - rotationCountClone[j] + 4;
                    }
                }

                // 다음 row가 돌려야할 횟수 (위에 행이 밑에 행한테 영향주므로 rotationcount 업데이트)
                for (int j = 0; j < N; j++) rotationCountClone[j] = mapClone[i,j];  
            }

            // 가능한 경우인지 확인
            for (int i = 0; i < N; i++) 
            {
                if (rotationCountClone[i] != 0) return; // 하나라도 12시방향 아니면 pass
            }
            answer = Math.Min(answer, totalRotationCount);
            return;
        }

        // 첫번째 행에 대해 회전수 정하기 (0, 90, 180, 270) => 모든 경우
        for (int i = 0; i < 4; i++) 
        {
            rotationCount[ind] = i; // 행에 대한 rotation count
            DFS(ind + 1);
        }
    }
}

결과