[C++/9555] 대회 장소 준비

---

⛔ 단순히 기록용 입니다... 어떻게 풀었는가 생각도 다시 해보고 그러니까 아마도 도움은 안되실 것 같습니다.

---

BFS를 이용한 문제 풀이입니다. 하지만, 한번 찾았던 학교는 절대 중복 체크를 하지 맙시다!

아래는 정답 코드입니다.그리고 return 값을 int로 던져주었을때 값이 틀리게 나왔는데 그 문제가 무엇인지 아직도 모르겠다.

#include<iostream>
#include<queue>
#include<cstring>

#define MAX 101
using namespace std;

const int dx[8] = {-1,0,1,-1,1,-1,0,1};
const int dy[8] = {-1,-1,-1,0,0,1,1,1};

int testCase,n,m,board[MAX][MAX],visited[MAX][MAX],schoolChk[MAX];

int isRange(int y, int x){
	return 0 <= y && y < n && 0 <= x && x < m;
}

void init() {
	
	memset(board,0,sizeof(board));
	
	cin >> n >> m;
	
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			cin >> board[i][j];
		}
	}
	
}

void bfs(int y, int x, int number) {
	
	visited[y][x] = 1;
	int chk = 0;
	queue<pair<int,int> > q;
	q.push({y,x});
	
	while(!q.empty()){
		
		int y = q.front().first;
		int x = q.front().second;
		q.pop();
		
		for(int i = 0; i < 8; i++){
			
			int ny = y + dy[i];
			int nx = x + dx[i];
			
			if(!isRange(ny,nx)) continue;
			if(visited[ny][nx]) continue;
			if(board[ny][nx] == -1) continue;
			if(board[ny][nx] != number) continue;
			
			chk = 1;
			visited[ny][nx] = 1;
			q.push({ny,nx});
			
		}
		
	}
	
	if(chk) schoolChk[number] = 1;
}

void solve() {
	
	int ans = 0;
	memset(visited,0,sizeof(visited));
	memset(schoolChk,0,sizeof(schoolChk));
	
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			if(!visited[i][j] && board[i][j] != -1){
				bfs(i,j,board[i][j]);
			}
		}
	}
	
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> testCase;
	
	while(testCase--){
	
		int ans = 0;
		
		init();
		solve();
		
		for(int i = 1; i <= 100; i++){
			if(schoolChk[i]) ans++;
		}
		
		cout << ans << "\n";
	}
	
	
	return 0;
}