DFS를 재귀함수로 구현하였다.
DP하려다 보니 재귀함수를 좀 잘 알 필요가 있어서 한번 구현하고 넘어갔다
pos구조체 만드니까 더 지저분해졌다.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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(); | |
} | |