[2D Array] Spiral Matrix

 

2D Array를 traverse 하는데에 아주 좋은 테크닉이 있어 정리를 해보려고 한다. 코드트리에서 수강한 내용으로, 바로 dx dy 테크닉이다.

 

문제를 보면 2D Array를 시계방향으로 순환하며 돌아야하는 형태이다. 여기서 index의 시계방향 전환을 쉽게 해주는 dx dy 테크닉이란, 

 

이렇게 좌표를 미리 세팅해주는 것을 뜻한다. 미리 dx와 dy 리스트를 만들어놓고 그 안에 방향값을 저장해놓으면, dx dy의 인덱스만 바꾸어도 x,y 좌표 방향을 한 번에 전환해줄 수 있다. 초기의 방향은 정하기 나름인데, 이 문제의 경우 일단 시작하면 동쪽으로 가기 때문에 동쪽을 0으로 놓고 초기 방향인 dir_num에 0을 할당해 주었다(dir_num = 0).

 

이때 중요한 것은 dx dy의 값은 리스트 matrix[i][j]의 i와 j로 생각해주어야 한다는 것이다. 그래서 오른쪽으로 한 칸 가면 row는 동일하고 col 인덱스는 하나 증가하기 때문에 0, 1

 

이 문제에서 생각할 것은, 방향대로 쭉 간다 / 벽에 막히거나 and 이미 방문한 노드일 경우 방향을 바꾼다.

그러기 위해서는 방문한 노드를 관리하는 visited 리스트가 필요하다. 

또한 matrix의 노드 갯수만큼 순환할 것이므로, 그리고 벽에 막히는지 체크(다음 인덱스가 matrix의 row / column range 안에 있는지)를 알기 위해 row 와 col 변수가 각각 있다.

 

그리고 x, y는 각각 0,0 (시작노드)로 할당해주고, 일단 방문한 후 넣고 시작한다. 그래야 밑에서 x, y 를 새로운 좌표(그다음 좌표)로 바꿔준 후에 다음 for loop에서 바로 넣어줄 수 있기 때문이다. 

또 주의할 점은 visited 리스트를 만들 때 내가 자꾸 이상하게 만드는데, [False]*row가 아니라 [False]*col in range row이다. 일단 col갯수만큼 False로 한 줄을 만들고 그 줄을 row만큼 반복해주는 것이기 때문이다.

 

기억할 것은: dx, dy 테크닉은 2D Array에 좋고 / [i][j]를 기준으로 값을 정해준다 / 초기 방향 설정과 각각의 방향 설정인 dir_num이 필요하다 / 시계방향 회전은 (dir_num + 1) % 4로 나머지가 4 밑으로 나오는 것을 이용해서 방향전환을 한다 / 방문기록을 체크하기 위해 초기에 False로 채워진 visited 배열이 필요하다.