[배열/시뮬레이션] 54. Spiral Matrix

문제 바로가기

Spiral Matrix - LeetCode

 

어제의 추천 문제입니다. 보다 더 머리를 쓰는 문제를 풀어야 실력이 향상될텐데... 퇴근하고 오면 머리쓰기가 왜이리 싫은지~~

 

2차원 배열이 주어지면 걔를 시계방향으로 삥삥 안으로 돌면서 리스트에 넣어주는 문제입니다. 이딴게 미디움???

그냥.. 가라는 대로 가면 됩니다. 다만 다음 칸이 갈 수 있는 칸인지 체크해주는게 관건!

 

class Solution {
  public int[] dy = {0, 1, 0, -1};
  public int[] dx = {1, 0, -1, 0};
  public boolean[][] visited;
  public int dir = 0;
  public int m, n;

  class Point {
    int y;
    int x;

    Point(int y, int x) {
      this.y = y;
      this.x = x;
    }

    Point next(int i) {
      return new Point(this.y + dy[i], this.x + dx[i]);
    }
  }

  public List<Integer> spiralOrder(int[][] matrix) {
    List<Integer> list = new ArrayList<>();
    m = matrix.length;
    n = matrix[0].length;
    visited = new boolean[m][n];

    Point cur = new Point(0, 0);
    visit(list, matrix, cur);    

    while (list.size() < m * n) {
      Point next = cur.next(dir);

      if (isIn(next, m, n) && !visited[next.y][next.x]) {
        cur = next;
        visit(list, matrix, cur);
      } else {
        dir = (dir + 1) % 4;
      }
    }

    return list;
  }

  private void visit(List<Integer> list, int[][] matrix, Point p) {
    list.add(matrix[p.y][p.x]);
    visited[p.y][p.x] = true;
  }

  private boolean isIn(Point p, int m, int n) {
    return 0 <= p.y && p.y < m && 0 <= p.x && p.x < n;
  }
}

 

쓸데없이 장황합니다ㅎ. 줄이라면 줄일 수 있는데.. Point 객체를 한 번 만들어봤습니다. 좌표와 관련된 역할과 책임을 모두 갖는.. 근데 방향 배열은 또 밖에 있넹ㅋ

 

이렇게 배열을 돌아다니는 문제는 보통 반복문을 돌리기 마련인데요, 이 문제는 종료 조건이 참 명료해서 좋습니다. 바로 리스트에 (m * n) 개가 들어가면 배열을 모두 구경했단 의미지요.

 

다음에 가려는 배열의 원소가 갈 수 있는 곳인지를 잘 체크해야 합니다.

1. 배열의 바깥으로 빠지진 않는지? (isIn())
2. 이미 방문했던 곳은 아닌지? (visited[][])

 

이렇게 다음에 방문할 곳을 잘 추려냈다면, 방문해주면 됩니다!! 리스트에 해당 원소의 값을 추가하고, 방문 체크를 해주면 됩니다.

 

 

다음부터는 쫌더... 쪼끔더... 짱구를 굴려야 하는 문제를.. 풀어보도록...........

감사합니다!!!!