[leetcode] Find All Groups of Farmland

문제

• 문제 링크
• 땅을 나타내는 이차원 배열 land가 주어진다. 각 배열 값은 0 또는 1을 갖는다. 0은 숲을 의미하고, 1은 농지를 의미한다. 농지는 전체 모양이 직사각형을 이루도록 구성되어 있고, 이를 group이라고 한다. group은 왼쪽상단의 좌표와 오른쪽하단의 좌표로 표현할 수 있다. 예를 들면 왼쪽상단 좌표가 (r1, c1)이고 오른쪽 하단 좌표가 (r2, c2)이면, (r1, c1, r2, c2)로 표현할 수 있다. land에 있는 모든 group을 찾아서 좌표로 반환해야 한다.
• 제약 조건
  • land 범위: 1 <= row, col <= 300
• 예시
  

풀이

풀기 전

• land를 순회하면서 값이 1인 농지를 만날 때마다 BFS 또는 DFS로 농지의 범위를 구하면 된다.

코드

class Solution {
    private int[] dy = {0, 0, 1, -1};
    private int[] dx = {1, -1, 0, 0};

    private int[] BFS(int[][] land, int i, int j) {
        int[] ret = {i, j, 0, 0};  // 반환할 농장 group의 좌표이다.

        Queue<Pair<Integer, Integer>> q = new LinkedList<>();
        q.add(new Pair(i, j));
        land[i][j] = 0;  // 방문한 농지를 0으로 변경해서 방문 표시로 사용한다.

        int y, x;
        while (!q.isEmpty()) {
            y = q.peek().getKey();
            x = q.peek().getValue();
            q.poll();

            ret[2] = Math.max(ret[2], y);  // 좌표를 갱신한다.
            ret[3] = Math.max(ret[3], x);  // 좌표를 갱신한다.

            int ny, nx;
            for (int k=0; k<4; k++) {
                ny = y + dy[k];
                nx = x + dx[k];

				// 다음 좌표가 범위를 벗어나거나 숲이면 건너뛴다.
                if (ny < 0 || ny >= land.length || nx < 0 || nx >= land[0].length || land[ny][nx] == 0) {
                    continue;
                }

				// 아직 방문하지 않은 농지면 방문한다.
                q.add(new Pair(ny, nx));
                land[ny][nx] = 0;
            }
        }
        return ret;
    }

    public int[][] findFarmland(int[][] land) {
        List<int[]> ans = new ArrayList<>();

        for (int i=0; i<land.length; i++) {
            for (int j=0; j<land[0].length; j++) {
            	// 농지를 만나면 BFS 탐색해서 좌표를 구한다.
                if (land[i][j] == 1)
                    ans.add(BFS(land, i, j));
            }
        }

        return ans.toArray(new int[ans.size()][]);
    }
}

푼 후

• 모든 농지를 최대 한 번씩 방문하기 때문에 시간 복잡도는 O(row * col)이다. BFS 실행 시 큐에는 최대 농지에 있는 좌표를 넣기 때문에 공간 복잡도는 O(row * col)이다.
• 사실 group이 직사각형 형태라는 게 정해져있기 때문에 모두 탐색할 필요 없이, 왼쪽, 오른쪽, 위, 아래로 어디까지 이어져 있는지만 찾아도 될 거 같다.