DFS 활용 Flood Fill

입력 

5

0 0 0 0 0

0 0 0 1 1

0 0 0 1 0

1 1 1 1 0

0 0 0 0 0

1 1 3

 

<출력>

3 3 3 3 3

3 3 3 1 1

3 3 3 1 0

1 1 1 1 0

0 0 0 0 0

 

 

 

0은 빈공간 1은 경계선 1,1은 색칠하고자 하는 위치 3은 칠할 숫자

 

 

struct Point{
	int row, col;
}

int D[4][2] = { {-1,0}, {1,0}, {0,-1}, {0,1} }; //상하좌우
int N, Board[MAX_N][MAX_N];

int main(){
	cin >> N;
    for(int i =0; i<N; i++){
    	for(int j=0; j<N; j++){
        	cin >> Board[i][j];
         }
     }
     
     int sr, sc, color;
     cin >> sr >> sc >> color;
     dfs(sr, sc, color);
     
     for(int i =0; i<N; i++){
    	for(int j=0; j<N; j++){
        	cout << Board[i][j] << ' ';
         }
         cout << endl;
     }    
     return 0;
     
 }

void dfs(int r, int c, int color) { //r,c : 시작위치
	bool visited[MAX_N][MAX_N] = {false}; //하나하나에 대해서 방문여부
    stack<Point> mystack;
    mystack.push({r,c});
    
    while(!mystack.empty()){
    	Point curr = mystack.top();
        mystack.pop();
        if(visited[curr.row][curr.row])continue;
        
        visited[curr.row][curr.col] = true;
        Board[curr.row][curr.col] = color;
        
        for(int i =0; i<4; i++){ //상하좌우
        	int nr = curr.row + D[i][0], nc = curr.col+D[i][1];
            if(nr < 0 || nr > N-1 || nc <0 || nc >N-1) continue; //경계 값 검사
            if(visited[nr][nc]) continue; 
            if(Board[nr][nc] == 1) continue;
            mystack.push({nr, nc});
        }
     }
 }

https://www.youtube.com/watch?v=M48Po-wTOpU