[LeetCode] 498. Diagonal Traverse

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

Diagonal Traverse - LeetCode

Diagonal Traverse - Medium

 

 

m x n 행렬에 수가 적혀있을때, 이 행렬을 위 그림과 같이 대각선방향 지그재그로 방문해 방문 순서대로 수를 출력하는 문제다.

일단 시작점은 우상향방향이고, 그 다음은 좌하향, 그 다음은 또 우상향, ... 으로 반복이 된다.

이를 수식으로 나타내면, 현재 좌표를 (y,x)라고 할 때, x+y가 짝수라면 우상향, 홀수라면 좌하향이 된다.

그리고 이게 각 줄의 끝에 도달하면 다음 줄로 넘어가도록 구현을 해줘야한다.

 

위 그림에서 우상향일 때를 먼저 보자.

1) (0,0) 에 있는 1에 도달했을때, (0,1)인 2로 넘어가야 한다.

2) 또, (0,2) 에 있는 3에 도달했을때는 (1,2) 에 있는 6으로 넘어가야 한다.

언제는 x좌표가 ++이고 언제는 y좌표가 ++이 되는데,

 

일단 1), 2) 둘을 살펴보면 둘다 y좌표는 0 이 되었다.

그리고 2) 일때는 x좌표가 n-1이 된걸 알 수 있다.

 

이를 보면, 먼저 x좌표를 확인해서 x==n-1 이라면 y++을,

x!=n-1 인데 y==0이라면 x++을 해주면 된다.

 

따라서 우상향일때, 즉, x+y가 짝수일때는

x==n-1 이라면 y++

x!=n-1 && y==0 이라면 x++

둘다 아니라면 x++, y--를 해주고,

 

비슷한 방식으로 좌하향일떄, 즉 x+y가 홀수일때는

y==m-1 이라면 x++

y!=m-1 && x==0 이라면 y++

둘다 아니라면 x--, y++을 해주자.

 

전체 풀이 코드

class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& mat) {
        vector<int> ret;
        int m=mat.size(), n = mat[0].size(), x=0, y=0;
        while (x<n && y<m) {
            ret.push_back(mat[y][x]);
            if ((x+y)&1) {
                if (y==m-1) x++;
                else if (x==0) y++;
                else x--,y++;
            } else {
                if (x==n-1) y++;
                else if (y==0) x++;
                else x++,y--;
            }
        }
        return ret;
    }
};