DFS란 무엇인가?
-다차원 배열에서 각 칸을 방문할때 깊이를 우선으로 방문하는 알고리즘
문제풀이에서 DFS의 활용방식은?
-Flood-Fill
-그래프 트리 탐색에서 활용
BFS vs DFS(방문 순서)
STL
#define X first
#define Y second
int board[512][512];
bool vis[512][512];
int n=7, m=10;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
stack<pair<int,int>> s;
vis[0][0] = 1;
s.push({0,0});
while(!s.empty()){
pair<int,int> cur = s.top(); s.pop();
for(int dir=0; dir<4; dir++){
int nx = cur.X + dx[dir];
int ny = cur.Y + dy[dir];
if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue();
if(vis[nx][ny] || board[nx][ny] != 1) continue();
vis[nx][ny] = 1;
s.push({nx,ny});
}
}
}