[C++] Parameter 관점에 Call by Value

LeetCode '200. Number of Islands' 를 아래와 같이 DFS 알고리즘으로 C++로 구현했을 때 parameter로 grid를 Call by Value인 vector<vector<char>> grid로 넘겨주면 48/49의 테스트 케이스가 통과되지만 마지막 1개의 테스트 케이스가 Time Limit Exceeded (TLE)로 통과를 못하게 된다. 아이디어 자체엔 문제가 없지만 Call by Value 즉, '&' 의 유무가 통과 유무를 좌우한다.

 

// Wrong Solution
class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size();
        int n = grid[0].size();

        vector<vector<bool>> visited(m, vector<bool>(n, false));

        int res = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!visited[i][j]) {
                    visited[i][j] = true;
                    if (grid[i][j] == '1') {
                        res++;
                        dfs(m, n, i, j, grid, visited);
                    }
                }
            }
        }

        return res;
    }

    void dfs(int m, int n, int row, int col, vector<vector<char>> grid, vector<vector<bool>>& visited) {
        vector<vector<int>> dir = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};

        for (int i = 0; i < dir.size(); i++) {
            int nr = row + dir[i][0];
            int nc = col + dir[i][1];
            if (0 <= nr && nr < m && 0 <= nc && nc < n && !visited[nr][nc]) {
                visited[nr][nc] = true;
                if (grid[nr][nc] == '1') {
                    dfs(m, n, nr, nc, grid, visited);
                }
            }
        }
    }
};

 

하지만 Call by Reference인 vector<vector> &grid로 parameter를 설정하면, 모든 테스트 케이스가 통과되는 것을 확인할 수 있다. 이 차이는 특히 recursive function을 구현할 때 염두해야한다. Call by Value로 parameter를 설정할 경우 recursive function이 호출될 때 마다 해당 parameter의 값을 복사하게 된다. 이 문제의 경우 TLE가 발생했지만, 경우에 따라선 Memory Limit Exceeded 가 발생할 수 도 있다. 복잡한 자료구조를 parameter로 전달해야할 경우엔 Call by Reference를 사용하는 것이 바람직하다.

 

// Correct Solution
class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size();
        int n = grid[0].size();

        vector<vector<bool>> visited(m, vector<bool>(n, false));

        int res = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!visited[i][j]) {
                    visited[i][j] = true;
                    if (grid[i][j] == '1') {
                        res++;
                        dfs(m, n, i, j, grid, visited);
                    }
                }
            }
        }

        return res;
    }

    void dfs(int m, int n, int row, int col, vector<vector<char>>& grid, vector<vector<bool>>& visited) {
        vector<vector<int>> dir = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};

        for (int i = 0; i < dir.size(); i++) {
            int nr = row + dir[i][0];
            int nc = col + dir[i][1];
            if (0 <= nr && nr < m && 0 <= nc && nc < n && !visited[nr][nc]) {
                visited[nr][nc] = true;
                if (grid[nr][nc] == '1') {
                    dfs(m, n, nr, nc, grid, visited);
                }
            }
        }
    }
};