문제 링크

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

문제 풀이

MxN 2차원 행렬을 탐색하면서 인접한 배추들의 집합을 출력하는 문제이며 bfs를 이용하여 다음과 같이 풀었다.

1. map을 탐색하면서 map[i][j] = 1 이면서 visited = false 인지 검사 즉, 배추가 있고 방문한적이 없는지 확인
2. 배추가 있다면 bfs() 함수를 실행시키고 cnt 증가
3. dfs() 함수를 통해서 현재위치에서 인접한곳에 배추가 있는지 탐색하면서 배추가 있다면 visited = true
4. 1~3 반복 후 cnt 출력

변수

• int m : 배추밭 가로 길이
• int n : 배추밭 세로 길이
• int k : 배추가 심어져 있는 위치의 개수
• int testCaseNum : 테스트 케이스의 개수
• int cnt : 필요한 배추지렁이의 수
• int map[MAX][MAX] : 배추밭
• bool visited[MAX][MAX] : 방문여부 확인을 위한 배열
• int dx[4] = { -1, 0, 1, 0 } : 변하는 행값에 대한 배열 ( 위, 오른쪽, 아래, 왼쪽 순서 )
• int dy[4] = { 0, 1, 0 ,-1 } : 변하는 열값에 대한 배열 ( 위, 오른쪽, 아래, 왼쪽 순서 )

함수

• void bfs(int x, int y) : 시작 위치를 입력받아 인접한 배추를 찾는 함수
• void init() : 각 테스트 케이스에 대해서 새로운 map 및 cnt 적용을 위해 초기화 해주는 함수

정답 코드

#include<iostream>
#include<queue>

#define MAX 51

using namespace std;

int map[MAX][MAX] = { 0, };
bool visited[MAX][MAX] = { false };

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

int m; // 배추밭 가로 길이
int n; // 배추밭 세로 길이
int k; // 배추가 심어져 있는 위치의 개수 
int testCaseNum; //테스트 케이스의 개수 
int cnt = 0; // 필요한 배추지렁이의 수 

void bfs(int x, int y) {
	queue<pair<int, int>> q;
	q.push(pair<int, int>(x, y));
	visited[x][y] = true;
	while (!q.empty()){
		pair<int, int> cur = q.front();
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = cur.first + dx[i];
			int ny = cur.second + dy[i];

			if (nx > -1 && ny > -1 && nx < m && ny < n && map[nx][ny] == 1 && visited[nx][ny] == false) {
				visited[nx][ny] = true;
				q.push(pair<int,int>(nx, ny));
			}
		}
	}
}

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

int main() {
	cin >> testCaseNum;

	for (int i = 0; i < testCaseNum; i++) {
		cin >> m >> n >> k;
		for (int j = 0; j < k; j++) {
			int temp;
			int temp2;
			cin >> temp >> temp2; // 배추가 심어져 있는 위치에 대한 좌표
			map[temp][temp2] = 1;
		}
		for (int j = 0; j < m; j++) {
			for (int t = 0; t < n; t++) {
				if (map[j][t] == 1 && visited[j][t] == false) {
					bfs(j, t);
					cnt++;
				}
			}
		}
		cout << cnt;
		cout << endl;
		init();
		

	}
}