본문 바로가기

카테고리 없음

[Algorithm] DFS recursive구현

DFS를 재귀함수로 구현하였다.
DP하려다 보니 재귀함수를 좀 잘 알 필요가 있어서 한번 구현하고 넘어갔다

pos구조체 만드니까 더 지저분해졌다.

#include <iostream>
#define ROW_MAX 5
int gGraph[ROW_MAX][ROW_MAX] =
{
{1,1,0,0,0},
{1,1,0,0,0},
{1,1,1,1,0},
{1,0,0,1,0},
{1,0,0,1,1}
};
int gvisited[ROW_MAX][ROW_MAX];
int gVisitedOrder = 0;
struct pos{
int row;
int coloumn;
};
using namespace std;
bool isInBoundary(pos current)
{
if (current.row >= 0 && current.row < ROW_MAX && current.coloumn >= 0 && current.coloumn < ROW_MAX)
{
return 1;
}
else
{
return 0;
}
}
void dfs(pos current)
{
if (gGraph[current.row][current.coloumn] == 0 || gvisited[current.row][current.coloumn] != false)
{
return;
}
gvisited[current.row][current.coloumn] = ++gVisitedOrder;
if (isInBoundary({ current.row - 1, current.coloumn }) == true)
{
dfs({ current.row - 1, current.coloumn });
}
if (isInBoundary({ current.row, current.coloumn-1 }) == true)
{
dfs({ current.row, current.coloumn-1 });
}
if (isInBoundary({ current.row + 1, current.coloumn }) == true)
{
dfs({ current.row + 1, current.coloumn });
}
if (isInBoundary({ current.row, current.coloumn+1 }) == true)
{
dfs({ current.row , current.coloumn+1 });
}
}
void printCheck(){
for (int i = 0; i < ROW_MAX; i++)
{
for (int j = 0; j < ROW_MAX; j++)
{
cout << gvisited[i][j] << " ";
}
cout << endl;
}
}
int main(void)
{
dfs({ 0, 0 });
printCheck();
}