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

 

알고리즘 분류: 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색

문제 링크: https://www.acmicpc.net/problem/1012

1012번: 유기농 배추

 

 

【 풀이 】

 

배추밭을 나타내는 배열(field), 방문한 배추밭을 나타내는 배열(isVisited), 상하좌우 방향을 나타내는 배열(way) 세 개의 2차원 배열을 활용해 bfs로 해결했다.

구체적인 문제 해결 과정은 다음과 같다.

 

1. 배추밭을 가로로 쭉 돌면서 배추가 심어져 있고 방문한 적 없는 곳의 위치 bfs 함수로 전달, 결과(worm) 1씩 증가
2. 전달된 위치는 방문처리 한 후 큐에 삽입
3. 방문한 위치는 다른 변수에 저장한 후, 큐에서 빼냄
4. 방문한 위치 기준으로 상하좌우로(1칸 이내) 배추가 심어져 있는 곳이 있는지 확인
5. 배추가 심어져있으며 방문한 적이 없는 곳이라면, 그 위치를 방문 처리하고 큐에 삽입
6. 큐가 빌 때까지(배추가 심어져 있는 인접한 모든 곳을 방문할 때까지) 반복
7. 큐가 비면 다시 1번부터 반복

 

주의할 점은 테스트 케이스마다 배열을 꼭 초기화시켜주어야 한다는 것이다.

 

 

 

【 코드 】

 

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

int worm;		//	지렁이의 개수, 결과
int cnt, n, m, T;

queue<pair<int, int>>q;

bool field[51][51];		//	배추밭
bool isVisited[51][51];		//	방문여부 확인 배열

int way[4][2] = {		//	상하좌우 방향을 나타내는 배열
	{1,0}, {-1,0}, {0,1}, {0,-1}
};

void init(int n, int m){		//	테스트 케이스마다 배열을 초기화 해주는 함수
	for(int i=0;i<n;i++)
		for (int j = 0; j < m; j++) {
			field[i][j] = false;
			isVisited[i][j] = false;
		}
}
void bfs(int y, int x) {
	isVisited[y][x] = true;		//	방문 확인
	q.push({ y,x });		//	방문한 곳을 큐에 삽입
	while (!q.empty()) {
		y = q.front().first;		//	방문한 곳 위치 저장
		x = q.front().second;
		q.pop();		//	위치 저장 후 큐에서 빼냄

		for (int w = 0; w < 4; w++) {
       		 // 방문한 위치 기준, 상하좌우로(1칸 이내에) 배추가 심어져있는 곳이 있는지 확인
       		 // 배추가 심어져있고, 방문한 적이 없는 곳이라면 그 위치 방문 및 큐에 삽입, 그 후 다시 반복
			int wy = y + way[w][0];
			int wx = x + way[w][1];
			if (wy >= 0 && wx >= 0 && wy < n && wx < m) {
				if (field[wy][wx] == true && !isVisited[wy][wx]) {
					isVisited[wy][wx] = true;
					q.push({ wy,wx });
				}
			}
		}
	}
}

int main(void) {
	cin >> T;
	for (int t = 0; t < T; t++) {
		worm = 0;
		cin >> n >> m >> cnt;
		init(n, m);
		for (int i = 0; i < cnt; i++) {
			int n1, n2;
			cin >> n1 >> n2;
			field[n1][n2] = true;
		}

		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				if (field[i][j] == true && !isVisited[i][j]) {
					bfs(i, j);
					worm++;
				}
		cout << worm << endl;
	}
	return 0;
}