[LeetCode] 827. Making A Large Island

LeetCode - 827. Making A Large Island 알고리즘 문제 풀이

분류

문제 링크 : https://leetcode.com/problems/making-a-large-island/

풀이

0과 1 값을 갖는 $N \times N$ 크기의 2차원 벡터가 주어진다.

0으로 되어있는 칸을 한 개만 선택하여 1로 바꾸었을 때, 상하좌우로 인접한 가장 긴 1의 길이를 구하는 문제이다.

예를 들어 아래와 같은 $2 \times 2$ 벡터가 있을 때

\begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}

(0, 1)을 1로 바꾸거나, (1, 0)을 1로 바꾸면 인접한 가장 긴 1의 길이는 3이 된다.

길이를 구하는 것은 DFS(또는 BFS)를 수행하여 쉽게 구할 수 있으나, 이 문제를 해결하기 위해 아래의 내용을 고민했다.

• DFS 한 사이클 동안 상하좌우 인접한 1이 있는 칸을 방문하며 가장 긴 길이 $L$을 구했을 때, 지금까지 방문한 모든 임의의 위치에서 DFS를 수행하여도 가장 긴 길이가 $L$임을 확인할 수 있어야 하고 이 과정은 $O(1)$에 수행되어야 한다.
  • DFS 사이클 당 방문하는 위치에 대해 넘버(num)값을 부여하고, acc[num]에 방문 길이 값을 저장한다.
  • 상하좌우로 인접한 1 위치들은 동일한 넘버(num)를 갖고 있다.
  • ex) (0, 0), (0, 1) 위치가 1로 넘버링 되었을 때, acc[number[0][0]]과 acc[number[0][1]]은 동일하게 acc[1]을 나타낸다.

소스 코드

const int dr[] = { -1, 1, 0, 0 };
const int dc[] = { 0, 0, -1, 1 };

class Solution {
    int acc[62505];
    int number[500][500];
    int num;
    bool visitedNum[62505];
    
    int N; // grid size (N x N)
    
    inline bool isRange(const int& r, const int& c) {
        return 0 <= r && r < N && 0 <= c && c < N;
    }
    
    int dfs(int r, int c, vector<vector<int>>& grid) {
        int fieldAcc = 1;
        number[r][c] = num;
        for (int d = 0; d != 4; ++d) {
            int nr = r + dr[d];
            int nc = c + dc[d];
            if (isRange(nr, nc) && number[nr][nc] == 0 && grid[nr][nc] == 1) {
                fieldAcc += dfs(nr, nc, grid);
            }
        }
        return fieldAcc;
    }
    
public:
    int largestIsland(vector<vector<int>>& grid) {
        // init
        int len = N * N;
        for (int i = 1; i <= len; ++i) {
            acc[i] = 0;
            visitedNum[i] = false;
        }
        num = 0;
        
        N = static_cast<int>(grid.size());
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                if (grid[i][j] == 1 && number[i][j] == 0) {
                    ++num;
                    acc[num] += dfs(i, j, grid);
                }
            }
        }
        
        int ans = acc[1];
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                if (grid[i][j] == 0) {
                    int sum = 1, useIdx[4], idx = 0;
                    for (int d = 0; d != 4; ++d) {
                        int nr = i + dr[d];
                        int nc = j + dc[d];
                        if (isRange(nr, nc) && !visitedNum[number[nr][nc]]) {
                            sum += acc[number[nr][nc]];
                            useIdx[idx++] = number[nr][nc];
                            visitedNum[number[nr][nc]] = true;
                        }
                    }
                    for (int k = 0; k < idx; ++k) {
                        visitedNum[useIdx[k]] = false;
                    }
                    if (ans < sum) {
                        ans = sum;
                    }
                }
            }
        }
        return ans;
    }
};

Result

Runtime: 204 ms, faster than 99.18% of C++ online submissions for Making A Large Island.
Memory Usage: 54.5 MB, less than 97.30% of C++ online submissions for Making A Large Island.