[C++] 27211: 도넛 행성

백준 온라인 저지 - 27211번: 도넛 행성

c++

풀이

신박한 BFS 문제!

모든 좌표를 돌면서, 0을 만나면 BFS를 수행해준다.
BFS를 수행할 때마다, bfs_count를 1씩 늘려준다.
한 번 BFS를 수행하면, 상하좌우로 이동하여 접근할 수 있는 0을 모두 1로 바꿔준다.

이 문제의 특징은 2차원 배열에서 보았을 때 범위 밖으로 나가면 반대편으로 들어온다는 것이다.

만약 (0, 4)에서 위로 한 칸 가게 되면, 일반적인 BFS에서는 범위를 벗어나게 되지만, 이 문제에서는 (4, 4)에 도달한 것으로 취급한다. 그림에서 빨간색 방향으로 나가면 반대쪽 빨간색으로 들어오게 된다.(파란색도 마찬가지)

따라서 BFS도중 좌표가 0보다 작아지거나 n 또는 m보다 커진다면, 반대편의 좌표로 수정해주면 된다.

마지막에 bfs_count를 출력하면 끝 !

코드

#include <iostream>
#include <queue>

using namespace std;

void input_data(void);
void find_section(void);
void bfs(int x, int y);

int n, m, bfs_count;
int planet[1001][1001];
int move_x[4] = {1, -1, 0, 0};
int move_y[4] = {0, 0, 1, -1};
queue<pair<int, int>> bfs_q;

int main(void)
{
	input_data();
	find_section();

	return (0);
}

void input_data(void)
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	
	int i = -1;
	while (++i < n)
	{
		int j = -1;
		while (++j < m)
		{
			cin >> planet[i][j];
			planet[i][j] *= -1;
		}
	}

	return ;
}

void find_section(void)
{
	int i = -1;
	while (++i < n)
	{
		int j = -1;
		while (++j < m)
			if (planet[i][j] == 0)
			{
				bfs_count++;
				bfs(i, j);
			}
	}

	cout << bfs_count << '\n';

	return ;
}

void bfs(int x, int y)
{
	bfs_q.push({x, y});
	planet[x][y] = 1;
	
	while (!bfs_q.empty())
	{
		int now_x = bfs_q.front().first;
		int now_y = bfs_q.front().second;
		bfs_q.pop();
		
		int i = -1;
		while (++i < 4)
		{
			int next_x = now_x + move_x[i];
			int next_y = now_y + move_y[i];
			if (next_x < 0)
				next_x = n - 1;
			else if (next_x >= n)
				next_x = 0;
			if (next_y < 0)
				next_y = m - 1;
			else if (next_y >= m)
				next_y = 0;
			if (planet[next_x][next_y] == 0)
			{
				planet[next_x][next_y] = 1;
				bfs_q.push({next_x, next_y});
			}
		}
	}
	
	return ;
}

성공 !