[LeetCode] 1992. Find All Groups of Farmland

https://leetcode.com/problems/find-all-groups-of-farmland/description/

Leetcode - Find All Groups of Farmland

문제 유형 : dfs/bfs, 행렬

문제 난이도 : Medium

 

 

문제

You are given a 0-indexed m x n binary matrix land where a 0 represents a hectare of forested land and a 1 represents a hectare of farmland.

To keep the land organized, there are designated rectangular areas of hectares that consist entirely of farmland. These rectangular areas are called groups. No two groups are adjacent, meaning farmland in one group is not four-directionally adjacent to another farmland in a different group.

land can be represented by a coordinate system where the top left corner of land is (0, 0) and the bottom right corner of land is (m-1, n-1). Find the coordinates of the top left and bottom right corner of each group of farmland. A group of farmland with a top left corner at (r1, c1) and a bottom right corner at (r2, c2) is represented by the 4-length array [r1, c1, r2, c2].

Return a 2D array containing the 4-length arrays described above for each group of farmland in land. If there are no groups of farmland, return an empty array. You may return the answer in any order.

 

0-Indexed의 m * n 이진 행렬이 주어진다. 0은 1헥타르의 숲, 1은 1헥타르의 농지이다.

농지의 관리를 위해, 직사각형 모양으로 농지가 그룹화되어 있습니다.

[왼쪽 위의 행, 왼쪽 위의 열, 오른쪽 아래의 행, 오른쪽 아래의 열]을 담은 2차원배열로 농지들의 그룹을 반환하시오. 순서는 상관없습니다.

농지가 없으면 빈 배열을 반환하면 됩니다.

 

풀이

너무나 전형적인 순회 문제이다.

2차원 배열을 순회하면서, 방문한 적도 없고 농지라면, dfs/bfs를 시작한다.

순회를 시작하기 전, 그룹 정보의 배열을 만든다. group = [i, j, i, j]이런 식으로,

그리고, group[2]와 group[3]의 정보를 dfs/bfs하는 도중, 업데이트하면 된다.

dfs/bfs가 끝나면, 정답 배열에 group을 넣는다.

 

코드

C++

class Solution {
public:
    vector<vector<int>> findFarmland(vector<vector<int>>& land) {
        int n = land.size();
        int m = land[0].size();
        vector<vector<bool>> visited(n, vector<bool>(m, false));
        int di[] = {1, -1, 0, 0};
        int dj[] = {0, 0, 1, -1};
        vector<vector<int>> ans;

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m ; j++) {
                if(land[i][j] == 1 && !visited[i][j]) {
                    vector<int> group = {i, j, i, j};
                    queue<pair<int, int>> q;
                    q.push({i, j});
                    visited[i][j] = true;

                    while(!q.empty()) {
                        auto curr = q.front();
                        q.pop();

                        for(int k = 0; k < 4; k++) {
                            int ni = curr.first + di[k];
                            int nj = curr.second + dj[k];

                            if(ni < 0 || ni >= n || nj < 0 || nj >= m || !land[ni][nj] || visited[ni][nj]) continue;
                            q.push({ni, nj});
                            visited[ni][nj] = true;
                            if(group[2] < ni) group[2] = ni;
                            if(group[3] < nj) group[3] = nj;
                        }
                    }
                    ans.push_back(group);
                }
            }
        }

        return ans;
    }
};

 

 

Go

func findFarmland(land [][]int) [][]int {
    n := len(land);
    m := len(land[0]);
    visited := make([][]bool, n);
    for i := range visited {
        visited[i] = make([]bool, m);
    }
    di := []int{1, -1, 0, 0};
    dj := []int{0, 0, 1, -1};
    ans := make([][]int, 0);

    q:= make([][2]int, 0);

    for i := 0; i < n; i++ {
        for j := 0; j < m; j++ {
            if land[i][j] == 1 && !visited[i][j] {
                q = append(q, [2]int{i, j});
                group := []int{i, j, i, j};

                for len(q) > 0 {
                    curr := q[0];
                    q = q[1:];
                    for k := 0; k < 4; k++ {
                        ni := curr[0] + di[k];
                        nj := curr[1] + dj[k];

                        if ni < 0 || ni >= n || nj < 0 || nj >= m || land[ni][nj] == 0 || visited[ni][nj] {
                            continue;
                        }

                        q = append(q, [2]int{ni, nj});
                        visited[ni][nj] = true;
                        if ni > group[2] {
                            group[2] = ni;
                        }
                        if nj > group[3] {
                            group[3] = nj;
                        }
                    }
                }
                ans = append(ans, group);
            }
        }
    }

    return ans;
}