[Leetcode] 54. Spiral Matrix

Identifying the Problem

출처 leetcode

 

주어진 mxn 2차원 행렬을 나선형으로 탐색하며

1차원 배열에 값을 저장해 리턴한다.

 

 

 

 

Organizing thoughts

MAIN IDEA : matrix를 탐색하는 좌표를 방향키로 조정하듯 조절한다.

 

그림을 보면 간단한 규칙을 알 수 있는데,

[1]

<행 오른쪽  위 도달 시> 방향은 아래로 바뀜

<행 오른쪽 아래 도달시> 방향은 왼쪽으로 바뀜

<행 왼쪽   아래 도달시> 방향은 위로 바뀜

<행 왼쪽   위 도달시> 방향은 오른쪽으로 바뀜

 

[2]

한번 끝에 도달하면, 끝의 index는 가운데 쪽으로 한 칸 움직인다.

 

Sourcecode

int* spiralOrder(int** matrix, int matrixSize, int* matrixColSize, int* returnSize)
{
    int* ans = malloc(sizeof(int)* *matrixColSize * matrixSize); //정답 array
    int i = 0; //정답 array index
    int up = 0; //윗 방향
    int down = 0; //아랫 방향
    int left = 0; //왼쪽 방향
    int right = 0; //오른쪽 방향
    
    int x = 0; //matrix x좌표
    int y = 0; //matrix y좌표
    
    int left_end = 0; //왼쪽 끝 index
    int right_end = * matrixColSize - 1; //오른쪽 끝 index
    int up_end = 0; //위쪽 끝 index
    int bottom_end = matrixSize - 1; //아래쪽 끝 index
    
    right = 1;
    
    if(*matrixColSize == 1 || matrixSize == 1) 
    {
        if(*matrixColSize == 1){right = 0; down = 1;}
         
        up_end--;
        bottom_end ++;
        left_end--;
        right_end++;
    }
    
  
    while(i < *matrixColSize * matrixSize)
    {       
        ans[i] = matrix[y][x];
        
        if(left == 1) x--;
        else if(right == 1) x++;
        else if(up == 1) y--;
        else if(down == 1) y++;
        
        if(x==left_end && y>up_end) //왼쪽 아래 끝 일때
        {
            left = 0; 
            up=1; 
            left_end++;
            
        }
        else if(x==right_end && y<bottom_end) //오른쪽 위 끝 일때
        {
            right = 0;
            down = 1;
            right_end--;
        }
        else if(y==up_end && x<right_end) //왼쪽 위
        {
            up = 0;
            right = 1;
            up_end++;
        }
        else if(y==bottom_end && x>left_end ) //오른쪽 아래 끝
        {
            down = 0;
            left = 1;
            bottom_end--;
        }
        
        if(bottom_end < up_end) bottom_end = -1; 
        
        i++;
    }
    *returnSize = i;
    
    
    return ans;
}

Mistake

• 행이나 열이 1줄인 경우를 생각 못했다.
• 66번줄의  if(bottom_end < up_end) bottom_end = -1는
  bottom_end 값이 up_end 보다 커지는 순간이 발생하는데, 이는 행이 홀수개인 경우 생기며,
  탐색하는 값이 오른쪽 아래 끝에 위치해 있다고 판단하게 된다.
  이 부분을 막기 위해, bottom_end를 -1로 바꿔 오른쪽 아래 끝 조건문에 걸리지 않게 했다.