[C++] 백준 1012: 유기농 배추

문제

[C++] 백준 1012: 유기농 배추 SILVER 2
https://www.acmicpc.net/problem/1012

 

---

 

접근 방법

이 문제는 배추(1)가 심어진 위치들이 주어졌을 때, 상하좌우로 연결된 배추 묶음(컴포넌트)의 개수를 구하는 문제이다.
즉, 연결 요소(Connected Component) 개수를 세면 되고,

한 묶음당 필요한 지렁이 수가 1마리이므로 배추 묶음의 개수가 곧 정답이 된다.

 

배추밭을 N × M 2차원 배열(graph)로 만든 뒤,
전체 칸을 순회하면서 배추가 있는 칸(값이 1)을 만나면 DFS를 실행한다.

 

DFS에서는 현재 위치를 기준으로 상하좌우를 탐색하며 연결된 배추들을 전부 방문 처리한다. (1→0으로 변경)
한 번 DFS를 시작했다는 건 “하나의 묶음을 전부 처리했다”는 뜻이므로 DFS 호출이 끝날 때마다 카운트(cnt)를 1 증가시키면 된다.

 

구현 시 주의할 점

• 입력에서 좌표가 (x, y)로 들어오므로, 배열에 저장할 때는 graph[y][x] = 1로 넣어야 좌표가 뒤집히지 않는다.
• DFS에서 이동할 좌표는 범위 체크를 먼저 하고, 그 칸에 배추가 없으면(0) 건너뛰어야 한다. (continue)
• 테스트 케이스마다 밭이 새로 주어지므로 graph.clear() 후 resize()로 매번 초기화해줘야 이전 케이스의 값이 섞이지 않는다.
  (초기화를 해주지 않고 resize만 하면 런타임에러가 뜬다.)

 

---

 

코드

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

int M, N, K;
vector<vector<int>> graph;

int dy[4] = { -1, 0, 1, 0 };  // 상하좌우
int dx[4] = { 0,-1, 0, 1 };

void dfs(int y, int x)
{
	// 탐색한 곳을 0으로 바꿔줌
	graph[y][x] = 0;

	for (int i = 0; i < 4; i++)
	{
		int yy = y + dy[i];
		int xx = x + dx[i];

		// 범위를 초과하거나 이동할 위치에 배추가 없다면
		if ((yy < 0 || N <= yy) || (xx < 0 || M <= xx)
			|| graph[yy][xx] == 0)
			continue;

		dfs(yy, xx);
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int test_case = 0;
	cin >> test_case;

	for (int t = 0; t < test_case; t++)
	{
		cin >> M >> N >> K;

		graph.clear();
		graph.resize(N, vector<int>(M, 0));
		for (int i = 0; i < K; i++)
		{
			int y = 0, x = 0;
			cin >> x >> y;

			graph[y][x] = 1;
		}

		int cnt = 0;
		for (int y = 0; y < N; y++)
		{
			for (int x = 0; x < M; x++)
			{
				if (graph[y][x] == 1)
				{
					dfs(y, x);
					cnt++;
				}
			}
		}
		cout << cnt << '\n';
	}
	return 0;
}