[BFS, 난이도 중하] 백준 1012번 유기농 배추

https://kimcoder.tistory.com/17

[BFS, 난이도 중하] 백준 2667번 단지번호붙이기

단지번호붙이기 문제와 풀이법이 비슷하다.

약간 차이점이 있다면 테스트 케이스가 있으며, 가로와 세로의 길이가 따로 주어진다는 것이다.

가로, 세로 따로 주어진다는 사실을 못보고, 단지번호붙이기 소스코드를 그대로 복붙해서 테스트케이스 반복문만 추가해줬다가 이유도 모른채 틀렸습니다 라는 문구를 보게 되는 피해자는 발생하지 않기를 빈다. 마치 나처럼

 

그리고 memset 함수로 테스트케이스마다 map,visited 배열을 초기화 해줘야 한다.

간혹 저번 케이스에 사용된 데이터를 그대로 사용하게 되는 위험한 경우가 발생할 수 있기 때문이다.

참고로 초기화 함수는 대표적으로 memset, fill 이 있다.

2차원배열을 초기화할 경우에는 memset이 편하다.

#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>
#include <stack>
#include <string>
#include <cstring>
using namespace std;
int map[51][51];
bool visited[51][51];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,-1,1 };
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int test;
	cin >> test;
	for (int t = 0; t < test; t++) {
		memset(map, 0, sizeof(map));
		memset(visited, false, sizeof(visited));
		int n, m, k;
		cin >> n >> m >> k;
		queue<pair<int, int> > q;
		for (int i = 0; i < k; i++) {
			int a, b;
			cin >> a >> b;
			map[a][b] = 1;
		}

		int group = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (map[i][j] == 1 && !visited[i][j]) {
					visited[i][j] = true;
					q.push(make_pair(i, j));
					while (!q.empty()) {
						int x = q.front().first;
						int y = q.front().second;
						q.pop();
						for (int k = 0; k < 4; k++) {
							if (x + dx[k] < 0 || x + dx[k] >= n || y + dy[k] < 0 || y + dy[k] >= m) continue;
							if (map[x + dx[k]][y + dy[k]] == 1 && !visited[x + dx[k]][y + dy[k]]) {
								q.push(make_pair(x + dx[k], y + dy[k]));
								visited[x + dx[k]][y + dy[k]] = true;
							}
						}
					}
					group++;
				}
			}
		}
		cout << group << "\n";
	}
}