알고리즘23 :: 블러드 필 알고리즘 전형적인 예제

1. #include <bits/stdc++.h>
2. using namespace std;
3. #define X first
4. #define Y second // pair에서 first, second를 줄여서 쓰기 위해서 사용
5. int board[502][502] =
6. {{1,1,1,0,1,0,0,0,0,0},
7. {1,0,0,0,1,0,0,0,0,0},
8. {1,1,1,0,1,0,0,0,0,0},
9. {1,1,0,0,1,0,0,0,0,0},
10. {0,1,0,0,0,0,0,0,0,0},
11. {0,0,0,0,0,0,0,0,0,0},
12. {0,0,0,0,0,0,0,0,0,0} }; // 1이 파란 칸, 0이 빨간 칸에 대응
13. bool vis[502][502]; // 해당 칸을 방문했는지 여부를 저장
14. int n = 7, m = 10; // n = 행의 수, m = 열의 수
15. int dx[4] = {1,0,-1,0};
16. int dy[4] = {0,1,0,-1}; // 상하좌우 네 방향을 의미
17. int main(){
18. ios::sync_with_stdio(0);
19. cin.tie(0);
20. queue<pair<int,int> > Q;
21. vis[0][0] = 1; // (0, 0)을 방문했다고 명시
22. Q.push({0,0}); // 큐에 시작점인 (0, 0)을 삽입.
23. while(!Q.empty()){
24. auto cur = Q.front(); Q.pop();
25. cout << '(' << cur.X << ", " << cur.Y << ") -> ";
26. for(int dir = 0; dir < 4; dir++){ // 상하좌우 칸을 살펴볼 것이다.
27. int nx = cur.X + dx[dir];
28. int ny = cur.Y + dy[dir]; // nx, ny에 dir에서 정한 방향의 인접한 칸의 좌표가 들어감
29. if(nx < 0 or nx >= n or ny < 0 or ny >= m) continue; // 범위 밖일 경우 넘어감
30. if(vis[nx][ny] or board[nx][ny] != 1) continue; // 이미 방문한 칸이거나 파란 칸이 아닐 경우
31. vis[nx][ny] = 1; // (nx, ny)를 방문했다고 명시
32. Q.push({nx,ny});
33. }
34. }
35. }

출처 : 바킹덕 블로그