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

1012번: 유기농 배추 (acmicpc.net)

1012번: 유기농 배추

---

이해하기 

 

이번 문제에서는 배추가 재배하는 땅이 행렬로 주어졌기 때문에 탐색을 인접 행렬로 해야하는 걸 쉽게 알 수 있었다. 배추가 심어져 있는 사이클 혹은 연결 요소의 개수를 구하는 문제이므로 탐색의 횟수를 구하면 된다. 

또 가로 길이와 세로 길이가 다를 수 있다는 점을 고려해야 하면서 문제의 난이도가 다른 탐색 문제들에 비해서 올라갔다.

 

인접행렬 DFS 코드 

void DFS(int v){
    //현재 노드 방문 
    visited[v] = 1;
    cout << v << " ";
    
    //현재 노드와 인접한 노드를 큐에 넣음
    for(int i=1; i<=n; i++ ){
        if(map[v][i] == 1 && visited[i] == 0){
            DFS(i);
        }
    }
}

 

[백준 1260번 C++] DFS와 BFS (tistory.com) 에서 풀었던 인접행렬을 이용한 코드이다. 

이때는 for문에 1부터 n까지만 탐색해서 인접한(1인 원소)를 찾으면 됐는 데, 

이 문제에서는 상하좌우를 탐색해줘서 재귀적으로 dfs를 호출해야한다. 

---

[백준] C++ 1012번 유기농 배추 (tistory.com)

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

---

최종 코드

#include <iostream>

using namespace std;

int n, m, k;
int map[51][51];
int visited[51][51];
//상하좌우를 탐색하기 위해
int ypos[] = {0,0,-1,1};
int xpos[] = {-1,1,0,0};

void DFS(int y, int x){
    visited[y][x] = 1;
    
    for(int i=0; i<4; i++){
        int nx = x + xpos[i];
        int ny = y + ypos[i];
        
        if( nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
        if(map[ny][nx] == 1 && visited[ny][nx] == 0) DFS(ny, nx);
    }
}

int main()
{
    int T;
    cin >> T;
    
    while(T--){
        cin >> n >> m >> k;
        
        //인접 행렬에 배추의 위치저장
        int x, y;
        for(int i=0; i<k; i++){
            cin >> x >> y;
            map[y][x] = 1;
        }   
        
        int count = 0;
        //DFS 탐색할 때마다 count 증가
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j] == 1 && visited[i][j] == 0) {
                    DFS(i, j);
                    count++;
                }
            }
        }
        cout << count << "\n";
        
        //초기화
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                map[i][j] = 0;
                visited[i][j] = 0;
            }
        }
    
    }
    return 0;
}