walls and gates 풀이

https://leetcode.com/problems/walls-and-gates/

문제 재정의

• m x n 배열이 들어온다.
  • m과 n은 각각 1보다 크거나 같고 250 보다 작거나 같다.
• 각 배열은 3가지 상태가 있다.
  • 통과하지 못하는 벽 (-1)
  • 빈 공간 (INF)
  • 게이트 (0)
• 장애물이 없는 공간에서 게이트까지의 길이를 채워라.

입출력

Input: [
    [2147483647,-1,0,2147483647],
    [2147483647,2147483647,2147483647,-1],
    [2147483647,-1,2147483647,-1],
    [0,-1,2147483647,2147483647]
]

Output: [
  [ 3,-1, 0, 1],
  [ 2, 2, 1,-1],
  [ 1,-1, 2,-1],
  [ 0,-1, 3, 4]
]

내 접근법

• BFS를 활용한다.
• 빈 큐를 생성한다.
• m x n만큼 순회한다.
• 빈 공간은 지나친다.
• 게이트를 만나면, 큐에 넣는다.
  • BFS의 시작점이 된다.
• BFS의 시작점부터 다음 내용을 반복한다.
  • 게이트 주변에 빈 공간이 있고, 해당 공간에 채워진 숫자가 시작점 게이트에서의 숫자보다 크다면 큐에 넣는다.
    • 조건에 만족하지 않으면, 당연히 큐에 넣지 않는다.
  • 큐에 넣어진 빈 공간의 숫자를 빼면서 해당 공간에 게이트에서 여태까지의 거리를 기록한다.

public void main() {
  큐<좌표> q = new 빈 큐();

    for(int i=0; i<m; i++) {
      for(int j=0; j<n; j++) {
            // 게이트인 경우에만 시작점에 넣는다.
            if(배열[i][j] == 0) {
        // 시작지점 좌표 넣기
              큐.enqueue(new {[i][j]});
      }
      }
    }

  while(큐가 비어있지 않다면) {
        좌표 현재좌표 = 큐.poll(); // 큐에서 빼기
        // 각각의 주변 좌표가 접근 가능한 유효한 좌표인지 검증
        if(배열의 x+1, x-1, y+1, y-1이 인덱스를 초과하지 않는다면) {
          // 빈 공간이며, 최단거리가 현재 계산된 거리보다 짧은지 검증
          if(배열의 숫자가 게이트웨이에서 현재까지의 거리보다 짧다면) {
                배열[y][x] = 배열[현재좌표.y][현재좌표.x] + 1;
          }
        }
  }
}

class Solution {
    public int m;
    public int n;

    public void wallsAndGates(int[][] rooms) {
        m = rooms.length; // y축
        n = rooms[0].length; // x축
        LinkedList<int[]> queue = new LinkedList<>();

        for(int y=0; y<m; y++) {
            for(int x=0; x<n; x++) {
                if(rooms[y][x] == 0) {
                    queue.offer(new int[] {y, x});
                }
            }
        }

        while(!queue.isEmpty()) {
            int[] coords = queue.poll();
            int y = coords[0];
            int x = coords[1];
            int distance = rooms[y][x] + 1;

            y = y + 1;
            if(isValid(y, x) && rooms[y][x] > distance) {
                rooms[y][x] = distance;
                queue.offer(new int[] { y, x });
            }
            y = y - 1;

            y = y - 1;
            if(isValid(y, x) && rooms[y][x] > distance) {
                rooms[y][x] = distance;
                queue.offer(new int[] { y, x });
            }
            y = y + 1;

            x = x + 1;
            if(isValid(y, x) && rooms[y][x] > distance) {
                rooms[y][x] = distance;
                queue.offer(new int[] { y, x });
            }
            x = x - 1;

            x = x - 1;
            if(isValid(y, x) && rooms[y][x] > distance) {
                rooms[y][x] = distance;
                queue.offer(new int[] { y, x });
            }
        }
    }

    public boolean isValid(int y, int x) {
        if(y < 0 || x < 0 || y >= m || x >= n) {
            return false;
        }

        return true;
    }
}