독 확산 시간 풀이 BFS – 주석추가

1. #include <stdio.h>
2. #pragma warning(disable:4996)
3. #include <queue>
4. using namespace std;
6. int N;//가로
7. int M;//세로
9. struct point
10. {
11. int x;
12. int y;
13. };
14. point sp; //시작위치
16. char map[1000][1000];//입력된것을 저장할 배열
17. char sel[1000][1000]; //방문 햇는지 정보를 저장할 배열
19. void resetsel()//방문정보를 reset할 함수. 지금은 필요 없지만 test set이 여러개 들어온다면 필요함.
20. {
21. for (int i = 0; i < M; i++)
22. {
23. for (int j = 0; j < N; j++)
24. {
25. sel[i][j] = 0;
26. }
27. }
28. }
30. int xx[4] = { -1, 1, 0, 0 };//4방향으로 확산하기 위한 벡터를 미리 만들어 놓습니다.
31. int yy[4] = { 0, 0, -1, 1 };
32. //que는 그냥 std를 씁니다.
33. queue<point> qpoint;
36. int Bfs()
37. {
38. int qsize = qpoint.size();
40. for (int i = 0; i < qsize; i++)//현재 que에 들어있는 만큼 확산
41. {
42. point p = qpoint.front(); //앞에것을 가쟈오고
43. qpoint.pop(); // 앞에것을 버립니다. 직접구현할때는 한번에 해도 됩니다.
44. sel[p.y][p.x] = 1;
45. for (int dir = 0; dir < 4; dir++) //확산하는 방향은 미리 정해놓은 벡터로 4방향만
46. {
47. point np;//새로운 포인트
48. np.x = p.x + xx[dir];
49. np.y = p.y+yy[dir];
50. if (np.x < 0 || np.y < 0 || np.x >= N || np.y >= M) continue; //map범위를 벗어나면 아무것도 안합니다.
51. if (sel[np.y][np.x] == 1) continue; //이미 방문한 곳이면 아무것도 안함.
52. if (map[np.y][np.x] == 'B')continue; //포인트가 벽이라면 아무것도 안함.
53. qpoint.push(np);//방문해야 하는곳이 맞다면 queue에 추가합니다.
54. }
55. }
57. //모두 완료 했다면 추가된 queue가 없을겁니다. 그럼 0리턴
58. return qpoint.size();
59. }
61. #define T (1)// 원래 문제는 Test Set이 여러개 들어옵니다.
62. int main(void)
63. {
64. freopen("input.txt", "r", stdin);
65. // Test Set 도 여러개고, 파일 용량이 크니, 복사하여 붙여넣기도 어렵고, 직접타이핑 넣는거는 불가능이요~
66. //그러니 freopen은 필수..
68. //입력 받는 부분
69. for (int t = 0; t < T; t++)
70. {
71. scanf("%d %d", &N, &M);
72. scanf("%d %d", &sp.x, &sp.y);
73. }
75. for (int i = 0; i < M; i++)
76. {
77. for (int j = 0; j < N; j++)
78. {
79. scanf(" %c", &map[i][j]);
80. }
81. }
83. resetsel();//방문정보를 reset할 함수. 지금은 필요 없지만 test set이 여러개 들어온다면 필요함.
85. qpoint.push(sp);//첫 시작 포인트를 넣습니다.
86. int cnt = 0;
87. while (Bfs()) //Bsf에서 리턴이 0 일때까지 확산합니다.
88. {
89. cnt++;
90. }
92. printf("%d", cnt);
94. return 0;
95. }