https://www.acmicpc.net/problem/1012
1012번: 유기농 배추
차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에
www.acmicpc.net
이문제는 요즘 나의 경악스러운 알고리즘 실력에 실망하던차에 내가 빠르게 풀 수 있는 문제였다. 아직 고수가 되긴 멀었지만 빨리 이런 문제쯤은 10분만에 해치울 수 있는 파워 프로그래머가 되고 싶다!!!!!
이 문제의 경우 여러방식으로 풀 수 있다. 나의 경우 일반적으로 성능이 나쁘지 않은 BFS를 사용해서 풀었다
자 이문제를 풀때는 처음 1인애를 만나면 루프를 돌면서 자신을 기준으로 갈 수 있는 모든 점들을 BFS로 접근하여 visited배열에 마킹합니다 visited 배열이 1로 마킹되면 다시 해당하는 곳을 접근 하지 않습니다 이렇게 빨간색으로 체크 된 1을 root로 나머지 1로마킹된 애들이 BFS 로서 빨갛게 1로 마킹된 애들부터 같은색깔안에 있는 영역으로 접근합니다.
#include <iostream>
#include <queue>
using namespace std;
bool cabbage[52][52];
int visited[52][52];
int main() {
int T; //테스트 케이스의 개수
int M, N, K;//M:가로길이 N:세로길이 K: 배추가 심어져있는 위치의 개수;'
cin >> T;
queue<pair<int, int>> bfsQueue;
for (int i = 0; i < T; i++) {
cin >> M >> N >> K;
for (int j = 0; j < M; j++) {
for (int k = 0; k < N; k++) {
cabbage[j][k] = 0;
visited[j][k] = 0;
}
}
for (int j = 0; j < K; j++) {
int temp1, temp2;
cin >> temp1 >> temp2;
cabbage[temp1][temp2] = 1;
}
int countnum = 0;
for (int j = 0; j < M; j++) {
for (int k = 0; k < N; k++) {
if (visited[j][k] == 1 && cabbage[j][k]==1)
continue;
else if(visited[j][k]==0 && cabbage[j][k]==1){
countnum += 1;
cabbage[j][k] = 1;
bfsQueue.push(pair<int, int>(j, k));
while (!bfsQueue.empty()) {
int firstn,secondn;
firstn = bfsQueue.front().first;
secondn = bfsQueue.front().second;
bfsQueue.pop();
if (firstn >= 1) {
if (visited[firstn - 1][secondn]==0 &&cabbage[firstn-1][secondn] == 1) {
bfsQueue.push(pair<int, int>(firstn - 1, secondn));
visited[firstn - 1][secondn] = 1;
}
}
if (secondn >= 1) {
if (visited[firstn][secondn - 1] == 0 && cabbage[firstn][secondn - 1]==1) {
bfsQueue.push(pair<int, int>(firstn, secondn - 1));
visited[firstn][secondn - 1] = 1;
}
}
if (visited[firstn + 1][secondn] == 0 && cabbage[firstn + 1][secondn]==1) {
bfsQueue.push(pair<int, int>(firstn + 1, secondn));
visited[firstn + 1][secondn] = 1;
}
if (visited[firstn ][secondn+1] == 0 && cabbage[firstn][secondn + 1]==1) {
bfsQueue.push(pair<int, int>(firstn , secondn+1));
visited[firstn][secondn + 1] = 1;
}
}
}
}
}
cout << countnum << '\n';
}
} for (int j = 0; j < M; j++) {
for (int k = 0; k < N; k++) {
cabbage[j][k] = 0;
visited[j][k] = 0;
}
}
for (int j = 0; j < K; j++) {
int temp1, temp2;
cin >> temp1 >> temp2;
cabbage[temp1][temp2] = 1;
}일단 이부분은 각 케이스의 접근할때 배열들을 초기화 한후 양배추가 위치한곳을 1로 체크해줍니다
for (int k = 0; k < N; k++) {
if (visited[j][k] == 1 && cabbage[j][k]==1)
continue;
else if(visited[j][k]==0 && cabbage[j][k]==1){
countnum += 1;
cabbage[j][k] = 1;
bfsQueue.push(pair<int, int>(j, k));
while (!bfsQueue.empty()) {
int firstn,secondn;
firstn = bfsQueue.front().first;
secondn = bfsQueue.front().second;
bfsQueue.pop();
if (firstn >= 1) {
if (visited[firstn - 1][secondn]==0 &&cabbage[firstn-1][secondn] == 1) {
bfsQueue.push(pair<int, int>(firstn - 1, secondn));
visited[firstn - 1][secondn] = 1;
}
}
if (secondn >= 1) {
if (visited[firstn][secondn - 1] == 0 && cabbage[firstn][secondn - 1]==1) {
bfsQueue.push(pair<int, int>(firstn, secondn - 1));
visited[firstn][secondn - 1] = 1;
}
}
if (visited[firstn + 1][secondn] == 0 && cabbage[firstn + 1][secondn]==1) {
bfsQueue.push(pair<int, int>(firstn + 1, secondn));
visited[firstn + 1][secondn] = 1;
}
if (visited[firstn ][secondn+1] == 0 && cabbage[firstn][secondn + 1]==1) {
bfsQueue.push(pair<int, int>(firstn , secondn+1));
visited[firstn][secondn + 1] = 1;
}
}
}
}이부분은 모든 배열을 돌면서 visited배열이 1로된 위치이거나 양배추가 심어지지않는 cabbage 가 0인쪽은 방문하지 않게 합니다 만약에 visited가 0이고 cabbage가 1이면 방문하게 합니다 그후 BFS를 위해 큐에다가 각각의 자식들을 집어넣고
BFS를 실행하여 인접한 모든 cabbage가 1인 요소들에 대하여 visited 배열을 1로 초기화 해줍니다