[BOJ] 1012 : 유기농 배추

Question

---

Solution

• DFS나 BFS를 활용하여 풀면 된다. (나는 BFS를 사용했다)
• 밭이 되는 int map[][]과 방문 처리할 bool visited[][] 선언한다.
• 입력으로 받아지는 배추의 위치를 map[][] = 1; 로 초기화 시켜준다.
• 탐색 알고리즘을 통하여 최소의 해를 구하면 된다.
• 주의! 두번째 실행할 경우 꼭 init()을 통하여 맵과 방문처리 하였던것을 다시 초기화 시켜주어야 한다.

---

Cord

#include <iostream>
#include <vector>
#include <queue>

#define SIZE 51

using namespace std;

int t, m, n, k;	// 입력 변수


int map[SIZE][SIZE];
bool visited[SIZE][SIZE];

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

int cnt;

void bfs(int _x, int _y)
{
	queue<pair<int, int>> q;
	q.push({_x, _y});
	visited[_y][_x] = true;
	cnt++;

	while (!q.empty())
	{
		pair<int, int> cur = q.front();
		q.pop();

		for (int i = 0; i < 4; i++)
		{
			int nextX = cur.first + dx[i];
			int nextY = cur.second + dy[i];

			if (0 <= nextX && nextX < m && 0 <= nextY && nextY < n)
			{
				if (map[nextY][nextX] && !visited[nextY][nextX])
				{
					q.push({nextX, nextY});
					visited[nextY][nextX] = true;
				}
			}
		}
	}
}

void init()
{
	cnt = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			map[i][j] = 0;
			visited[i][j] = false;
		}
	}
}

int main()
{
	// 테스트 케이스의 수
	cin >> t;
	for (int c = 0; c < t; c++)
	{
		cin >> m >> n >> k;
		
		// 배추 심기
		for (int i = 0; i < k; i++)
		{
			int x, y;
			cin >> x >> y;
			map[y][x] = 1;
		}

		// BFS 실행
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				if (map[i][j] && !visited[i][j])
				{
					bfs(j, i);
				}
			}
		}

		// 결과 출력
		cout << cnt << '\n';
		init();	// 초기화
	}

	return 0;
}

---

Result

초기화 시켜주지 않아서 한참 헤맸다…