[백준] C# 16926번 배열 돌리기1

 

 

문제 이해

해당 문제는 같이 회전시킬 좌표들을 하나의 리스트로 인식하여, 회전시킬 수 있어야 한다.

예제 입력 1을 예로 들면 2차원 배열을 아래의 두 리스트로 분리한다.

• 1,2,3,4,8,12,16,15,14,13,9,5
• 2,3,7,11,10,6

이후 회전 시켰다는 것은, 앞에 요소를 다시 뒤로 돌려주면 된다.

• 1,2,3,4,8,12,16,15,14,13,9,5,1,2
• 2,3,7,11,10,6,2,3

여기까지 진행했다면, 각 배열별로 회전시킨 것과 동일하기 때문에 배열 순서대로 2차원 배열로 만들어주면 된다.

 

풀이

1. 배열의 시작점이 될 좌표(앵커)를 선정해야 한다.

/// 앵커가 될 수 있는 최대 값은 축이 짝수면 /2 하고 -1을 해야한다.
/// 만약 /2만 하면 축이 4일때 2값이 리턴되는데 2는 이미 2차원 배열상 중앙을 넘어선 값이기 때문에 -1을 해줘야한다.
int GetAnchorMax(int num)
{
    return num % 2 == 0 ? (num / 2) - 1 : num / 2;
}

/// 앵커로써 가질수 있는 최대값을 기준으로 x축과 y축 모두 넘지 않는 값으로 앵커를 잡아야한다.
/// 만약 maxX = 2, maxY = 1이라면 (0,0), (1,1)만 가능하고 (2,2)는 불가능하다.
List<(int, int)> GetAnchorList(int maxX, int maxY)
{
    var anchorList = new List<(int, int)>();
    var max = Math.Min(maxX, maxY);
    for (int i = 0; i <= max; i++)
    {
        var x = Math.Min(maxX, i);
        var y = Math.Min(maxY, i);

        anchorList.Add((x, y));
    }

    return anchorList;
}

 

여기서 내가 문제를 풀때 반드시 x축 혹은 y축 중 하나는 짝수라는 부분을 놓쳐서 앵커를 만드는 과정에서 애먹었는데, 짝수이기 때문에 반드시 앵커는 (0,0), (1,1), (2,2)와 같이 x좌표와 y좌표가 같은 값을 가진다는 것을 알 수 있다.

예제 입력 1을 예로 들면 (0,0), (1,1) 이 앵커가 된다. (2,2)는 될 수 없다. (2,2)를 기준으로 회전시킬 수 없다는 뜻이다.

만약 7x6 배열이라면 다음과 같이 (0,0) (1,1) (2,2) 좌표가 앵커가 된다.

 

2. 앵커를 기준으로 2차원 배열을 시계방향으로 돌면서 하나의 배열임을 인식해야 한다.

var cellList = new List<(int, int)>();
var valueList = new List<int>();

//시작 앵커 좌표 x,y
var startX = anchorList[i].Item1;
var startY = anchorList[i].Item2;

//시작 앵커 좌표로부터 한바퀴 회전할때 x좌표와,y좌표의 최대 값.
var maxAnchorX = N - startX - 1;
var maxAnchorY = M - startY - 1;

//시작 앵커 좌표로부터 우, 하, 좌, 상 순으로 하나의 배열로 만든다.
//오른쪽으로 이동
for (var curY = startY; curY <= maxAnchorY; curY++)
{
    cellList.Add((startX, curY));
    valueList.Add(baseMatrix[startX, curY]);
}

//아래로 이동
for (var curX = startX + 1; curX <= maxAnchorX; curX++)
{
    cellList.Add((curX, maxAnchorY));
    valueList.Add(baseMatrix[curX, maxAnchorY]);
}

//왼쪽으로 이동
for (var curY = maxAnchorY - 1; curY >= startY; curY--)
{
    cellList.Add((maxAnchorX, curY));
    valueList.Add(baseMatrix[maxAnchorX, curY]);
}

//위로 이동
for (var curX = maxAnchorX - 1; curX > startX; curX--)
{
    cellList.Add((curX, startY));
    valueList.Add(baseMatrix[curX, startY]);
}

만약 (0,0) 좌표에서 시작한 시계방향 배열은 가장 바깥쪽만 인식해야하고 (1,1)에서 시작한 배열은 그로부터 한칸 안쪽이어야한다.(2,2)는 가장 바깥으로부터 두칸 안쪽이라는 뜻이다.

즉 현재 시작한 좌표에서 오른쪽으로 이동할때는 x좌표는 유지하고 y좌표만 움직이고 거기서 아래로 움직일때는 y좌표는 유지하되, x좌표만 움직여야 하는데. 이때 x좌표와 y좌표값은 시작 앵커에 맞춰 안쪽으로 들어와 있어야하기 때문에 최대값이 지정되어야만 한다.

최대값을 구하는 방법은 다음과 같다.

• x축 최소값과 최대값 : 시작 x좌표, (x축길이 - 시작 x좌표 - 1)
• y축 최소값과 최대값 : 시작 y좌표, (y축길이 - 시작 y좌표 - 1)

-1를 뒤에 한 이유는 배열의 시작이 0이기 때문이다.

위 방법대로 최대값을 구한다면 만약 4x4배열에서 (0,0) 좌표로 시작한 배열의 최대 x좌표값은 4-0-1로 3이고 y좌표값도 4-0-1로 3이다.

즉 x는 0에서 3까지 y도 0부터 3까지이기 때문에 아래와 같은 방법으로 하나의 배열이 나오는것을 알 수 있다.

• y증가 : (0,0) -> (0,1) -> (0,2) -> (0,3), - > (0,4) y좌표 최대값 오버
• x증가 : (1,3) -> (2,3) -> (3,3) -> (4,3) x좌표 최대값 오버
• y감소 : (3,2) -> (3,1) -> (3,0), -> (-1,3) y좌표 최소값 언더
• x감소 : (2,0) -> (1,0) -> (0,0) 시작 앵커

위와 같이 2차원 배열을 돌면 나온 값이 하나의 배열임을 알 수 있다.

(1,1) 좌표로 시작하는 배열도 위와 같은 방법으로 확인할 수 있는데 적으면 다음과 같다.

최대 x값과 y은 위와 같은 방법으로 각각 4-1-1, 4-1-1 => 2,2 임을 알 수 있다.

• y증가 : (1,1) -> (1,2) -> (1,3) y좌표 최대값 오버
• x증가 : (2,2) -> (3,2) x좌표 최대값 오버
• y감소 : (2,1) -> (2,0) y좌표 최소값 언더
• x감소 : (1,1) 시작 앵커

동일한 방식으로 (1,1) - (1,2) - (2,2) - (2,1) 좌표가 하나의 배열임을 구할 수 있다.

 

3. 이렇게 리스트로 나온 좌표값의 값들을 K만큼 회전시킨다

void ApplyRotate(List<int> valueList, int K)
{
    for (int i = 0; i < K; i++)
    {
        var value = valueList[0];
        valueList.RemoveAt(0);
        valueList.Add(value);
    }
}

 

4. 회전된 값을 그대로 새로운 matrix에 적용한다.

//회전된 배열을 그대로 적용
for (int k = 0; k < cellList.Count; k++)
{
    var cell = cellList[k];
    matrix[cell.Item1, cell.Item2] = valueList[k];
}

 

풀면서 놓친점

앵커리스트를 만드는데 굉장히 많은 시간을 썼다. 문제에 반드시 짝수축을 가진다는 부분을 좀더 빠르게 캐치했다면 쉽게 풀 수 있었을 것 같다.

 

최종 코드

//Input N,M,K
var inputs = Console.ReadLine().Split(" ");
var N = int.Parse(inputs[0]);
var M = int.Parse(inputs[1]);
var K = int.Parse(inputs[2]);

//Input Matrix
var inputMatrix = new int[N, M];
for (int i = 0; i < N; i++)
{
    var arrays = Console.ReadLine().Split(" ");
    for (int j = 0; j < arrays.Length; j++)
    {
        inputMatrix[i, j] = int.Parse(arrays[j]);
    }
}

//앵커의 맥스값 리턴.
var maxX = GetAnchorMax(N);
var maxY = GetAnchorMax(M);

//앵커리스트 리턴.
var anchorList = GetAnchorList(maxX, maxY);

//회전된 2차원 배열 리턴.
int[,] matrix = GetMatrix(N, M, K, inputMatrix, anchorList);

//Output
for (int i = 0; i < matrix.GetLength(0); i++)
{
    for (int j = 0; j < matrix.GetLength(1); j++)
    {
        Console.Write(matrix[i,j] + " ");
    }
    
    Console.WriteLine();
}

/// 앵커가 될 수 있는 최대 값은 축이 짝수면 /2 하고 -1을 해야한다.
/// 만약 /2만 하면 축이 4일때 2값이 리턴되는데 2는 이미 2차원 배열상 중앙을 넘어선 값이기 때문에 -1을 해줘야한다.
int GetAnchorMax(int num)
{
    return num % 2 == 0 ? (num / 2) - 1 : num / 2;
}

/// 앵커로써 가질수 있는 최대값을 기준으로 x축과 y축 모두 넘지 않는 값으로 앵커를 잡아야한다.
/// 만약 maxX = 2, maxY = 1이라면 (0,0), (1,1)만 가능하고 (2,2)는 불가능하다.
List<(int, int)> GetAnchorList(int maxX, int maxY)
{
    var anchorList = new List<(int, int)>();
    var max = Math.Min(maxX, maxY);
    for (int i = 0; i <= max; i++)
    {
        var x = Math.Min(maxX, i);
        var y = Math.Min(maxY, i);

        anchorList.Add((x, y));
    }

    return anchorList;
}

int[,] GetMatrix(int N, int M, int K, int[,] baseMatrix, List<(int, int)> anchorList)
{
    int[,] matrix = new int[N, M];
    //현재 앵커를 기준으로 한바퀴를 돌면서 리스트 만들기.
    for (int i = 0; i < anchorList.Count; i++)
    {
        var cellList = new List<(int, int)>();
        var valueList = new List<int>();

        //시작 앵커 좌표 x,y
        var startX = anchorList[i].Item1;
        var startY = anchorList[i].Item2;
        
        //시작 앵커 좌표로부터 한바퀴 회전할때 x좌표와,y좌표의 최대 값.
        var maxAnchorX = N - startX - 1;
        var maxAnchorY = M - startY - 1;

        //시작 앵커 좌표로부터 우, 하, 좌, 상 순으로 하나의 배열로 만든다.
        //오른쪽으로 이동
        for (var curY = startY; curY <= maxAnchorY; curY++)
        {
            cellList.Add((startX, curY));
            valueList.Add(baseMatrix[startX, curY]);
        }

        //아래로 이동
        for (var curX = startX + 1; curX <= maxAnchorX; curX++)
        {
            cellList.Add((curX, maxAnchorY));
            valueList.Add(baseMatrix[curX, maxAnchorY]);
        }

        //왼쪽으로 이동
        for (var curY = maxAnchorY - 1; curY >= startY; curY--)
        {
            cellList.Add((maxAnchorX, curY));
            valueList.Add(baseMatrix[maxAnchorX, curY]);
        }

        //위로 이동
        for (var curX = maxAnchorX - 1; curX > startX; curX--)
        {
            cellList.Add((curX, startY));
            valueList.Add(baseMatrix[curX, startY]);
        }

        ApplyRotate(valueList, K);

        //회전된 배열을 그대로 적용
        for (int k = 0; k < cellList.Count; k++)
        {
            var cell = cellList[k];
            matrix[cell.Item1, cell.Item2] = valueList[k];
        }
    }

    return matrix;
}


void ApplyRotate(List<int> valueList, int K)
{
    for (int i = 0; i < K; i++)
    {
        var value = valueList[0];
        valueList.RemoveAt(0);
        valueList.Add(value);
    }
}