#include #include #include using namespace std; void BFS(queue>& qBFS, vector>& vCheck, vector>& dxdy, int i, int j, int N, int M, vector< vector >& vField) { //1. 탐색을 시작할 위치를 queue에 담기 qBFS.push({ i,j }); //2. BFS while (!qBFS.empty()) { //2.1 꺼낸다 vector vCurrent = { (qBFS.front())[0], (qBFS.front())[1] }; // i,j qBFS.pop(); int nX = 0, nY = 0; //2.2 해당 노드와 인접한 노드를 방문한다. for (int i = 0; i < 4; i++) { //2.2.1 방문 좌표 계산 nX = vCurrent[0] + dxdy[i][0]; nY = vCurrent[1] + dxdy[i][1]; //2.2.2 방문 좌표가 현재 방문이 가능한 상황인지 ( 바운더리 바깥 , 방문했었는지, 배추가 존재하는지 ) if (!((nX < 0) || (nX >= N) || (nY < 0) || (nY >= M) || vCheck[nX][nY] || (vField[nX][nY] == 0))) { vCheck[nX][nY] = true; qBFS.push({ nX, nY }); } } } return; } int main(void) { int T = 0; cin >> T; vector< vector > dxdy = { {1,0} , {-1,0}, {0,1}, {0,-1} }; for (int TestCase = 0; TestCase < T; TestCase++) { // 0. Variable int answer = 0; int M = 0, N = 0, K = 0; cin >> M >> N >> K; // N * M ( row * column ) , 배추는 K개 // 1. 밭 선언 및 채우기 vector< vector > vField(N, vector(M, 0)); { int X = 0, Y = 0; for (int i = 0; i < K; i++) { cin >> X >> Y; vField[Y][X] = 1; } } for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { cout << vField[i][j] << " "; } cout << "\n"; } //2. 밭에 들어갈 흰지렁이 마리 수 찾기 //2.1 BFS를 위한 variable 작성 //2.1.1 방문 체크 배열 작성 vector< vector > vCheck(N, vector(M, false)); // vCheck[i][j]가 false -> 방문한 적 없음. //2.1.2 Queue queue> qBFS; //2.2 BFS를 통한 배추 구획 탐색 for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { //해당 구역에 배추가 없거나, 이미 방문했다면, BFS를 하지 않는다. if ((vField[i][j] == 0) || vCheck[i][j]) continue; else { //2.2.1 BFS 가능 지역 도달 -> answer에 +1 answer++; //2.2.2 BFS BFS(qBFS, vCheck, dxdy, i, j, N, M, vField); } } } //3. 벌레 개수 출력 cout << answer << "\n"; } }

제출 #12649

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: