ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 1012.유기농 배추
    알고리즘/백준 BAEK JOON 2020. 5. 26. 00:33

    이번에 풀어볼 문제는 백준의 1012 유기농 배추이다! 이 문제는 BFS나 DFS를 이용해서 풀면 되는데

    역시나 난이도는 높지않다. 여기서 배울 점은 나눠진 영역의 탐색(BFS, DFS)을 진행하는 방법이다.

    BFS를 기준으로 설명을 적어놓았다 -> DFS든 BFS든 탐색방법만 다를 뿐 구현 로직은 같다.

     

    1012번: 유기농 배추

    차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 �

    www.acmicpc.net

    이 문제에서 Key Point는 1. 맵에 배추를 잘 넣어주는 로직 2. 영역별로 나눠져 있는 배추를 탐색하는 것이다. 


    1번은 간단하기 때문에 조금만 생각하면 가능니까 PASS하고

    2번의 경우는 map에 배추부분을 "1"이라는 숫자로 표현해놓고 탐색으로 발견될 때마다 map의 "1"을 지워주며 탐색하는 것이다. 

    그렇게 되면 map을 전부 탐색하며 배추 부분만 찾게될 것이고 붙어있는 배추끼리는 이미 BFS 함수를 통해 배추표시가

    "1" -> "0"으로 지워져있기 때문에 몇가지 영역으로 나눠있는지 확인할 수 있게된다. 마지막엔 당연히 map의 배추가 다 지워진다.

    < Code 설명 - DFS>

    #pragma warning(disable:4996)
    #include <iostream>
    #include <queue>
    #include <string.h>
    #include <algorithm>
    #define MAX 51
    
    using namespace std;
    int t, m, n, k;
    
    int map[MAX][MAX];
    
    int dx[4] = { 0, 0, 1, -1 };
    int dy[4] = { 1, -1, 0, 0 };
    
    void zilong(int a, int b){
    	map[a][b] = 0; // 배추를 만나면 해당배추는 벌레가 갔으므로 0으로 셋팅
    	queue<pair<int, int>>bechu; //BFS 탐색을 위한 queue
    	bechu.push(make_pair(a, b));//해당 배추좌표를 시작으로 하기위해 queue에 넣음
    	while (!bechu.empty()){
    		int x = bechu.front().first; // x좌표 이용
    		int y = bechu.front().second;// y좌표 이용
    		bechu.pop();
    		for (int i = 0; i < 4; i++){ // 상하좌우 탐색
    			int ax = x + dx[i];
    			int ay = y + dy[i];
    			if (ax < 0 || ay < 0 || ax >= m || ay >= n)
    				continue; // map 범위 내에 없으면 넘김
    			if (map[ax][ay] == 1){ // 배추가 있으면
    				map[ax][ay] = 0;   // 배추를 0으로 바꿔주고
    				bechu.push(make_pair(ax, ay)); 
                                    // 해당 좌표 queue에 저장
    			}
    		}
    	}
    }
    
    int main(){
    	//freopen("1012.txt", "r", stdin);
    	cin >> t;
    	
    	int a, b, cnt;
    	for (int z = 0; z < t; z++){
    		cin >> m >> n >> k;
    		cnt = 0;
    		memset(map, 0, sizeof(map));   //map 초기화
    
    		for (int i = 0; i < m; i++){
    			for (int j = 0; j < n; j++){
    				map[i][j] = 0; // 우선 전부다 0으로 저장한다.
    			}
    		}
    
    		for (int i = 0; i < k; i++){
    			cin >> a >> b;
    			map[a][b] = 1; // 배추가 있는 곳은 1로 저장
    		}
    
    		for (int i = 0; i < m; i++){
    			for (int j = 0; j < n; j++){
    				if (map[i][j] == 1){ // 배추가 있는 곳은
    					zilong(i, j);    // 탐색을 시작한다.
    					cnt+=1; 
                        // 탐색중에 배추를 찾으면 map[i][j]=0이 됨
                        // 그러므로 영역을 구분할 수 있다.
    				}
    			}
    		}
    		cout << cnt << "\n";
    	}
    	return 0;
    }

     

     

     

     


     

     

    < Code 설명 - BFS>

    #pragma warning(disable:4996)
    #include <iostream>
    #include <string.h>
    #include <stack>
    
    
    #define MAX 51
    using namespace std;
    
    
    int t, m, n, k;
    int map[MAX][MAX];
    
    int dx[4] = { 0, 0, 1, -1 };
    int dy[4] = { 1, -1, 0, 0 };
    
    void search(int a, int b){
    	map[a][b] = 0;
    	stack<pair<int, int>>s;
    	s.push(make_pair(a,b));
    	int x = s.top().first;
    	int y = s.top().second;
    	while (!s.empty()){
    		for (int i = 0; i < 4; i++){
    			int ax = x + dx[i];
    			int ay = y + dy[i];
    			if (ax < 0 || ay < 0 || ax > m || ay > n)
    				continue;
    			if (map[ax][ay] == 1){
    				map[ax][ay] = 0;
    				s.push(make_pair(ax, ay));
    				x = s.top().first;
    				y = s.top().second;
    				i = -1;
    			}
    		}
    		if (!s.empty()){
    			s.pop();
    			if (!s.empty()){
    				x = s.top().first;
    				y = s.top().second;
    			}
    		}
    
    	}
    }
    int main() {
    	//freopen("1012.txt", "r", stdin);
    	cin >> t;
    	int cnt;
    	for (int z = 0; z < t; z++){
    		cin >> m >> n >> k;
    		cnt = 0;
    		memset(map, 0, sizeof(map));
    		
    		for (int i = 0; i < m; i++){
    			for (int j = 0; j < n; j++){
    				map[i][j] = 0;
    			}
    		}
    		int a, b;
    		for (int i = 0; i < k; i++){
    			cin >> a >> b;
    			map[a][b] = 1;
    		}
    
    		for (int i = 0; i < m; i++){
    			for (int j = 0; j < n; j++){
    				if (map[i][j] == 1){
    					search(i, j);
    					cnt++;
    				}
    			}
    		}
    		cout << cnt << "\n";
    	}
    	return 0;
    }
    

    # BFS 대신 DFS를 쓰는 것말고 나머지는 같으므로 설명은 생략하겠다..

     

     

     


     

     

    < Code 설명 - 재귀>

    #pragma warning(disable:4996)
    #include <iostream>
    #include <string.h>
    #include <queue>
    
    
    #define MAX 51
    using namespace std;
    
    
    int t, m, n, k;
    int map[MAX][MAX];
    
    int dx[4] = { 0, 0, 1, -1 };
    int dy[4] = { 1, -1, 0, 0 };
    
    queue<pair<int, int>>q;
    void search(int a, int b){
    	if (q.empty())
    		return;
    	map[a][b] = 0;
    	int x = q.front().first;
    	int y = q.front().second;
    	q.pop();
    	for (int i = 0; i < 4; i++){
    		int ax = x + dx[i];
    		int ay = y + dy[i];
    		if (ax<0 || ay<0 || ax>=m || ay>=n)
    			continue;
    		if (map[ax][ay] == 1){
    			map[ax][ay] = 0;
    			q.push(make_pair(ax, ay));
    			search(ax, ay);
    		}
    	}
    }
    int main() {
    	//freopen("1012.txt", "r", stdin);
    	cin >> t;
    	int cnt;
    	for (int z = 0; z < t; z++){
    		cin >> m >> n >> k;
    		cnt = 0;
    		memset(map, 0, sizeof(map));
    
    		for (int i = 0; i < m; i++){
    			for (int j = 0; j < n; j++){
    				map[i][j] = 0;
    			}
    		}
    		int a, b;
    		for (int i = 0; i < k; i++){
    			cin >> a >> b;
    			map[a][b] = 1;
    		}
    
    		for (int i = 0; i < m; i++){
    			for (int j = 0; j < n; j++){
    				if (map[i][j] == 1){
    					q.push(make_pair(i, j));
    					search(i, j);
    					cnt++;
    				}
    			}
    		}
    		cout << cnt << "\n";
    	}
    	return 0;
    }
    

    # 요것도 똑같다:)

     

    '알고리즘 > 백준 BAEK JOON' 카테고리의 다른 글

    1697.숨바꼭질  (0) 2020.05.27
    2468.안전영역  (0) 2020.05.26
    1012.유기농 배추  (0) 2020.05.26
    7576.토마토  (0) 2020.05.25
    14502.연구소  (0) 2020.05.25
    2667.단지번호붙이기  (0) 2020.05.21

    댓글 0

Designed by Tistory.