DFS(Depth First Search)
시작하는 칸을 "스택"에 넣고 방문했다는 표시를 남김
"스택"에서 원소를 꺼내어 그 칸과 상하좌우로 인접한 칸에 대해 3번을 진행
해당 칸을 이전에 방문했다면 아무것도 하지않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 스택에 삽입
"스택"이 빌 때까지 2번을 반복
비록 최종적인 방문 결과는 똑같아도, 방문 순서에서 차이가 있다.
거리를 계산할 때는 DFS를 사용할 수 없음. BFS로만 거리계산 가능
#include <bits/stdc++.h>
using namespace std;
int board[502][502] = {...};
bool vis[502][502];
int n= 7, m = 10;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
int main(void)
{
stack<pair<int,int>> s;
vis[0][0] = 1;
s.push({0,0});
while(!s.empty()){
pair<int,int> cur = s.top();
s.pop();
cout << '(' << cur.first << ', ' << cur.second << ") ->";
for(int i=0; i<4; i++){
int x = cur.first + dx[i];
int y = cur.second + dy[i];
if(x < 0 || x >= n || y < 0 || y >= m)
continue;
if(vis[x][y] || board[x][y] != 1)
continue;
vis[x][y] = 1;
s.push({x,y});
}
}
}