[C++] DFS의 구현

[Settpark]

• DFS는 아래와 같이 구현하고, BFS와 달리 Queue대신 Stack을 사용한다.

int board[502][502];
int vis[502][502];
    
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
    
int m = 7, n = 10;

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    stack<pair<int, int>> St;
    vis[0][0] = 1;
    St.push({0,0}); // *1
    
    while(!St.empty()) {
        auto cur = St.top(); St.pop();
        
        for (int i = 0; i < 4; i++) {
            int nx = cur.first + dx[i];
            int ny = cur.second + dy[i];
            
            if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
            if (vis[nx][ny] || board[nx][ny] != 1) continue;
            vis[nx][ny] = 1;
            St.push({nx,ny});
        }
    }    
}

• 자꾸 *1 부분 BFS나 DFS나 구현할 때 깜박하는 데, 저거 안하면 애초에 시작도 안된다.