[LeetCode]Diagonal Traverse

https://leetcode.com/problems/diagonal-traverse/description/

LeetCode - The World's Leading Online Programming Learning Platform

 

문제 분석

주어진 m*n 그리드를 대각선 위 대각선 아래로 반복하면서 탐색하는 순서를 구하는 문제입니다.

 

처음 시도한 답안

class Solution:
    def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
        r = len(mat)
        c = len(mat[0])
        i, j = 0, 0
        answer = []
        up_right = True

        for idx in range(r*c):
            answer.append(mat[i][j]) # 방문지점 기록

            if up_right: # 대각선 위로가는 경우
                i = i - 1
                j = j + 1
            else: # 대각선 아래로 가는 경우
                i = i + 1
                j = j - 1

            if i >= r: # i가 row보다 큰 값으로 벗어나는 경우
                i -= 1
                j += 2
                up_right = True # 다음부턴 대각선 위로 가야함

            elif j >= c: # j가 col 보다 큰 값으로 벗어나는 경우
                i += 2
                j -= 1
                up_right = False # 다음부턴 대각선 아래로 가야함
                
            elif i < 0: # i가 음수로 벗어나는 경우
                i += 1 # or i = 0
                up_right = False # 다음부턴 대각선 아래로 가야함

            elif j < 0: # j가 음수로 벗어나는 경우
                j += 1 # or j = 0
                up_right = True # 다음부턴 대각선 위로 가야함

        return answer

접근 방법

1. 0,0 위치에서 대각선 위와 대각선 아래로 가는 경우를 번갈아 가면서 좌표를 이동하는 순서를 기록합니다.
2. up_right 변수는 대각선 위로 가는 경우에 True, 대각선 아래로 가는 경우에 False 값을 가지게 됩니다.
3. 초기에는 0,0의 위치에서, 대각선 위로 가는 경우로 설정합니다.
4. row * col의 수만큼 순회합니다.
   1. 방문한 지점을 answer에 기록합니다.
   2. 대각선 위로 올라가는 경우라면 i-1, j+1의 위치로 이동하게 합니다.
   3. 대각선 아래로 가는 경우라면 i+1, j-1의 위치로 이동하게 합니다.
   4. 만약 i가 r값과 같거나 커지는 경우라면 (대각선 아래로 가면서 아래로 벗어나는 경우)
      1. i-1, j+2의 위치로 이동하고 대각선 위로 이동할 수 있도록 설정합니다.
   5. 만약 j가 c값과 같거나 커지는 경우라면 (대각선 위로 올라가면서 오른쪽으로 벗어난 경우)
      1. i+2, j-1의 위치로 이동하고 대각선 아래로 이동할 수 있도록 설정합니다.
   6. 만약 i가 0보다 작은 경우라면 (대각선 위로 올라가면서 위를 벗어나는 경우)
      1. i를 0으로 만들거나 +1 시키고 대각선 아래로 이동할 수 있도록 설정합니다.
   7. 만약 j가 0보다 작은 경우라면 (대각선 아래로 내려가면서 왼쪽을 벗어나는 경우)
      
      1. j를 0으로 만들건나 +1 시키고 대각선 위로 이동할 수 있도록 설정합니다.
5. 방문한 순서인 answer를 Return 합니다.

0,0 위치에서 시작해서 움직여야 하는 대각선 방향 변수를 통해서 좌표를 벗어나는지 체크후 이동하면 되는 문제입니다. 하지만 한가지 주의해야할 점은 i < 0, j < 0인 조건은 i >= r, j >= c 조건보다 뒤에 위치해야 합니다. 

 

즉, 오른쪽과 아래로 벗어나는 경우의 처리가 먼저 되어야 합니다. (위와 왼쪽으로 벗어나면 1칸만 이동하면 되는데 오른쪽과 아래는 여러칸을 이동해야 합니다.)

글로만 설명하면 이해가 쉽지 않으니 그림과 함께 설명하겠습니다.



만약, i < 0인 조건을 먼저 처리하게 된다면

3(0, 2) 지점에서 대각선 위로 계속해서 다음 좌표를 탐색하면 (-1, 3)이 됩니다. 그리고 i = 0으로 초기화하면 (0, 3)의 좌표가 되는데 이 값은 Matrix를 벗어난 값이 되게 됩니다.

따라서 (-1, 3)에서 j >= c인 조건을 먼저 처리함으로써 (1, 2) 지점인 6으로 정상적으로 탐색이 가능합니다.

 

처음에는 반복하는 인덱스가 짝수인지 홀수인지를 판단해 대각선 방향을 조절하려고 했으나 그 방법으로는 풀이할 수 없었습니다. 따라서 대각선 이동 방향의 변수를 선언하고 위치를 이동한 뒤 matrix를 벗어나면 조정해주는 방향으로 풀이했습니다.