[Graphs] DFS.2 -Number of Islands

https://leetcode.com/problems/number-of-islands/

Number of Islands - LeetCode

이번에는 Graph문제에서 인접행렬을 이용한 풀이를 알아보자.

 

• 구하고자 하는것 : 섬의 갯수인데 행렬에서 "1"의 집합을 구한다고 보면된다
• 문제 풀이 구조 : 인접행렬 구조!

 

1. 첫번쨰 문제풀이 방식

class Solution {
public:
    int m; // 2by2 matrix 필요
    int n;
    vector<vector<char>> grid; // grid 생성
    vector<vector<int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    // 요건 어디다가 써줄려나? -> DFS에서 상하좌우로 이동해줄떄 쓰기위한 벡터자료형성이구나
    vector<vector<bool>> seen; // 지나친것들 체크
    
    int numIslands(vector<vector<char>>& grid) {
        this->grid = grid; //this 라는 object를 불를때, variable과 중복되니까 this-> 로
        m = grid.size();
        n = grid[0].size();
        seen = vector(m, vector<bool>(n, false));
        
        int ans = 0;
        for (int row = 0; row < m; row++) {
            for (int col = 0; col < n; col++) {
                if (grid[row][col] == '1' && !seen[row][col]) {
                    ans++;
                    seen[row][col] = true;
                    dfs(row, col);//봤다는 처리해줘야하니
                }
            }
        }
        
        return ans;
    }
    
    void dfs(int row, int col) { //대단함.. 연결되는 노드를 다검색할수있도록 recursion 일으키기
        for (vector<int>& direction: directions) {
            int nextRow = row + direction[0], nextCol = col + direction[1];
            if (valid(nextRow, nextCol) && !seen[nextRow][nextCol]) {
            //여기서 valid()가 필요한데 이는 범위를 벗어날경우를 대비함! 버그가 날확률이높은문구
                seen[nextRow][nextCol] = true;
                dfs(nextRow, nextCol);
            }
        }
    }
    
    bool valid(int row, int col) {
        return 0 <= row && row < m && 0 <= col && col < n && grid[row][col] == '1';
    }
};

 

2. 두번쨰 방법으로  DFS를 iterative 방식으로 하는법

void dfs(int startRow, int startCol) {
    stack<pair<int, int>> stack; // stack 내부 변수를 [int,int]로 생성하여 전달할수있도록하는 문법
    stack.push(pair(startRow, startCol));

    while (!stack.empty()) {
        auto[row, col] = stack.top();
        stack.pop();
        for (vector<int>& direction: directions) {
            int nextRow = row + direction[0], nextCol = col + direction[1];
            if (valid(nextRow, nextCol) && !seen[nextRow][nextCol]) {
                seen[nextRow][nextCol] = true;
                stack.push(pair(nextRow, nextCol));
            }
        }
    }
}

 

 

 

---

wrap-up points

• 인접행렬일 경우 2x2 matrix로 dfs 돌릴 구조를 생각.
• seen vector를 생성하여 2x2 matrix를 체크한지 않한지 판단넣기.
• m부터 n까지 for 구문으로 돌리면서 이안에 dfs 함수 집어넣기.
• dfs에 필요한 valid 함수 따로 생성하기. 
•