백준 4963 c++ -[PlusUltraCode]

[필자 사고]

 

전형적인 그래프 탐색 문제이다.

 

다른 문제와 달리 특이한 점은 대각선의 이동경로 또한 탐색해야 된다는 점이다.

 

평소 접했던 문제는 동 서 남 북 총 4방향만 탐색경로로 지정 했다면 이 문제는 
대각선까지 고려해야 된다.

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

수학에서 배웠떤 1사분면 (1,0)에서 시작하여 반시계 방향으로 4사분면 (1,-1) 까지 이동경로를 넣어놓은 배열이다.

 

나머지는 BFS() 탐색으로 문제를 쉽게 풀 수 있다.

 

[소스 코드]

 

#include <iostream>
#include <vector>
#include<queue>
using namespace std;

int dx[8] = {1,1,0,-1,-1,-1,0,1};
int dy[8] = { 0,1,1,1,0,-1,-1,-1, };
vector<vector<int>> Arr;
vector<vector<bool>> visited;

bool Inside(int seroSize, int garoSize, int sero,int garo) {
	if (sero >= 0 && sero < seroSize && garo >= 0 && garo < garoSize)return true;
	return false;
}

void BFS(int seroSize, int garoSize) {
	queue<pair<int, int>> myQueue;
	
	int count = 0;
	for (int y = 0; y < seroSize; y++) {
		for (int x = 0; x < garoSize; x++) {
			if (visited[y][x] == false && Arr[y][x] == 1) {
				count++;
				myQueue.push({ y,x });
				visited[y][x] = true;

				while (!myQueue.empty()) {
					int nowSero = myQueue.front().first;
					int nowGaro = myQueue.front().second;
					myQueue.pop();

					for (int i = 0; i < 8; i++) {
						int nextSero = nowSero + dy[i];
						int nextGaro = nowGaro + dx[i];
						if (Inside(seroSize, garoSize, nextSero, nextGaro) &&
							visited[nextSero][nextGaro] == false &&
							Arr[nextSero][nextGaro] == 1) {
							visited[nextSero][nextGaro] = true;
							myQueue.push({ nextSero,nextGaro });
						}
					}
				}
			}
		}
	}
	cout << count << '\n';
}

void Init(int sero, int garo) {
	Arr.clear();
	visited.clear();
	Arr.resize(sero);
	visited.resize(sero);
	for (int i = 0; i < sero; i++) {
		Arr[i].resize(garo);
		visited[i].resize(garo, false);
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	while (1) {
		int garo, sero;
		cin >> garo >> sero;
		if (garo == 0 && sero == 0)return 0;
		Init(sero, garo);
		
		for (int i = 0; i < sero; i++) {
			for (int k = 0; k < garo; k++) {
				cin >> Arr[i][k];
			}
		}
		BFS(sero,garo);
	}
}