[백준(BOJ)] 1012번 : 유기농 배추 - C++[CPP]

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

1012번: 유기농 배추

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

 

---

 

⊙ 문제 접근 과정

 

BFS 알고리즘 돌리고 T만큼 반복해야하니 reset()이라는 초기화 함수를 만들어줬다.

---

 

⊙ 문제 풀이

 

#include <iostream>
#include <queue>

using namespace std;
#define MAX 51

int M,N,K;
int arr[MAX][MAX]={0,};
int visited[MAX][MAX]={0,};
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};
queue<pair<int,int>> q;

void bfs(int x,int y) {
    q.push({x,y});
    while(!q.empty()) {
        int a = q.front().first;
        int b = q.front().second;
        q.pop();
        visited[a][b]=true;
        for(int i=0;i<4;i++) {
            int nx = a + dx[i];
            int ny = b + dy[i];
            if(0<=nx && 0<=ny && nx <N && ny < M && !visited[nx][ny]&& arr[nx][ny]==1) {
                q.push({nx,ny});
                visited[nx][ny]=true;
            }
        }
    }
}

void reset() {
	while (!q.empty()) q.pop();
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			visited[i][j] = false;
			arr[i][j] = 0;
		}
	}
}
int main() {
    int T;
    cin >> T;

    for(int t=0;t<T;t++) {
        reset();

        cin >>M >> N >> K;
        int cnt=0;

        for(int i=0;i<K;i++) {
            int x,y;
            cin >> y >> x;
            arr[x][y]=1;
        }

        for(int i=0;i<N;i++) {
            for(int j=0;j<M;j++){
                if(arr[i][j]==1 && !visited[i][j]) {
                    bfs(i,j);
                    cnt++;
                }
            }
        }
    cout << cnt << "\n";
    }
}

---

⊙ 결과

 

---

⊙ 마무리

 

 

NONE

 

좋아요는 로그인하지 않아도 누를 수 있습니다!