[백준] 11123: 양 한마리... 양 두마리...

문제 링크

https://www.acmicpc.net/problem/11123

접근 방식 / 풀이

전형적인, 배열로 진행하는 dfs / bfs 문제이다.

입력이(#)인 곳은 양이 있으므로 1, 입력이(.)인 곳은 양이 없으므로 0으로 입력받는다.
입력 받은 뒤, 모든 곳을 순환하면서 방문하지 않은 곳 중에서 양이 있는 곳이 있다면 넓이 우선 탐색(bfs)를 진행하여 해당 노드와 인접한 모든 노드들을 방문시켜준다.
visited 배열은, 같은 그룹을 재방문하지 않기 위해서 작성하는 배열이다. 이 문제에서 노드는 한 번 방문한 이후 재사용할 필요성이 없기에, 양이 있는 곳을 방문했다면, visited 배열을 따로 작성할 필요 없이 처음 입력받은 배열을 0(양이 없음)으로 바꿔주어 같은 그룹을 재방문하지 않게 해준다.

bfs를 진행할 때마다 count를 1씩 늘려 주어 총 몇 개의 그룹이 있는 지 파악하면 되는 문제이다.

답안 코드 링크 (Github)

Github Solution Link

정답 코드

#include <iostream>
#include <string>
#include <queue>
#include <algorithm>
#define fastio                      \
	ios_base::sync_with_stdio(false); \
	cin.tie(NULL);                    \
	cout.tie(NULL)
using namespace std;

bool map[101][101];
int height, width;
void bfs(int init_x, int init_y);

int main(void)
{
	int t_case, check = 0;
	string s;

	fastio;
	cin >> t_case;
	while (t_case--)
	{
		cin >> height >> width;
		check = 0;
		for (int i = 0; i < height; i++)
		{
			cin >> s;
			for (int j = 0; j < width; j++)
				if (s[j] == '#')
					map[i][j] = 1;
		}
		for (int i = 0; i < height; i++)
			for (int j = 0; j < width; j++)
				if (map[i][j])
				{
					bfs(i, j);
					check++;
				}
		cout << check << "\n";
	}
	return (0);
}

void bfs(int init_x, int init_y)
{
	queue<pair<int, int>> q;
	pair<int, int> dir[4] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
	pair<int, int> node;
	int tmp_x, tmp_y;

	q.push({init_x, init_y});
	map[init_x][init_y] = false;
	while (!q.empty())
	{
		node = q.front();
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			tmp_x = node.first + dir[i].first;
			tmp_y = node.second + dir[i].second;
			if (tmp_x >= 0 && tmp_y >= 0 && tmp_x < height && tmp_y < width && map[tmp_x][tmp_y])
			{
				map[tmp_x][tmp_y] = false;
				q.push({tmp_x, tmp_y});
			}
		}
	}
}