[Algorithm] dfs 간단 구현 (단지 번호 문제)

dfs최대한 풀어서 구현해 보았다.

 

에러나면

row들어갈 자리에 column이 써져 있는지 잘 확인 해봐야한다.

 

인덱스가 array범위 안에 들어가는지 체크하는 함수를 뺄 수 있다.

 

visited 체크하는 부분이 애매한데 

단지가 아닌 곳은 visited체크하지 않고 dfs가 시작할때 visited체크를 해준다.

 

visited체크를 스택에서 뺄때 처리할지 스택에 넣을때 처리 할지도 정할수 있는데

스택에 넣을때 체크하여 스택에 중복되는것이 없게 하는 것이 좋다. 

#include< iostream>
using namespace std;
 
#define arrSize 7
int maze[arrSize][arrSize] =
{ { 0, 0, 1, 0, 1, 0, 1 }
, { 1, 1, 1, 0, 1, 0, 0 }
, { 0, 0, 0, 0, 1, 1, 1 }
, { 0, 0, 0, 0, 0, 0, 0 }
, { 1, 1, 1, 1, 1, 1, 0 }
, { 1, 0, 0, 0, 0, 1, 1 }
, { 1, 0, 0, 0, 0, 0, 1 } };
 
int visited[arrSize][arrSize] = { 0, };
 
int dr[4] = { 0, 0, 1, -1 };
int dc[4] = { 1, -1, 0, 0 };
 
int rowStack[100] = { 0, };
int rowStackTop = 0;
int colummStack[100] = { 0, };
int colummStackTop = 0;
 
void dfs(int row, int column, int danzi)
{
    if (visited[row][column] == 1)
    {
        return;
    }
    rowStack[rowStackTop++] = row;
    colummStack[colummStackTop++] = column;
    maze[row][column] = danzi;
    visited[row][column] = 1;
    while (rowStackTop != 0)
    {
        int tempRow = rowStack[--rowStackTop];
        int tempColumn = colummStack[--colummStackTop];
 
        int nr = 0;
        int nc = 0;
        for (int i = 0; i < 4; i++)
        {
            nr = tempRow + dr[i];
            nc = tempColumn + dc[i];
            if (nr >= 0 && nr < arrSize&&nc >= 0 && nc < arrSize && visited[nr][nc] == 0 && maze[nr][nc] != 0)
            {
                visited[nr][nc] = 1;
                rowStack[rowStackTop++] = nr;
                colummStack[colummStackTop++] = nc;
                maze[nr][nc] = danzi;
            }
        }
    }
}
int main(void)
{
    int danzi = 5;
    for (int row = 0; row < arrSize; row++)
    {
        for (int column = 0; column < arrSize; column++)
        {
            if (maze[row][column] != 0 && visited[row][column] == 0)
            {
                cout << "hi" << endl;
                dfs(row, column, danzi++);
            }
        }
    }
 
    for (int row = 0; row < arrSize; row++)
    {
        for (int column = 0; column < arrSize; column++)
        {
            cout << maze[row][column] << " ";
        }
        cout << endl;
    }
    cout << endl;
}