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

1012번: 유기농 배추

---

문제 이해하기

 문제가 길어보이지만, 핵심만 요약해보면,

서로 인접해있는 배추들이 몇 군데로 퍼저있는지 구하여라.

라고 할 수 있습니다.

 

 쉽게 말해, 배추들이 몇 개로 뭉쳐있는지를 구하는 문제입니다.

 이러한 인접 요소(Connected Component)의 수를 구하는 문제는 DFS또는 BFS를 통해 해결할 수 있습니다. 이 문제에서는 DFS를 사용하여 풀어보도록 하겠습니다. 

---

시간복잡도 어림하기

DFS 알고리즘

  이 문제에서는 그래프를 인접 행렬을 통해 구현합니다. 인접 행렬을 통해 구현한 그래프에서 DFS 알고리즘을 사용하면 O(N^2)의 시간복잡도가 걸립니다. 이 문제에서는 밭의 영역이 n x n이 아니라 n x m이고, n과 m이 최댓값이 50이므로 50의 제곱인 2500이 DFS의 시간복잡도가 됩니다.

 

 이는 제한 시간내해 해결하기 충분하 수치이므로 DFS알고리즘을 사용하여 문제를 해결해 보도록 하겠습니다.

---

알고리즘 설계하기

  우선 코드의 흐름을 설계해봅시다.

1.입력 받기
2. 모든 영역을 탐색하면서 DFS 실행
3. 연결 요소 개수 출력

으로 크게 세 부분으로 나눌 수 있습니다. 사실 입력 받기와 출력부분은 간단해서 설계가 큰 의미가 없는 부분입니다. 따라서 DFS 부분을 집중적으로 설계해보겠습니다.

 

 우선 어떤 지점부터 DFS를 진행할지 결정해야합니다. 주어진 밭 전체에서 연결 요소의 개수를 구해야 하는 문제이므로 결국 모든 지점을 기준으로 DFS를 진행해야합니다. 이때, 이미 방문한 지점이나 배추가 아닌 지점은 탐색을 하면 안 됩니다. 배추들의 연결 요소를 구하는 문제이기 때문입니다. 코드로는 다음과 같이 구현되겠네요.

for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
        if(배추가 아니라면 or 이미 방문한 땅이라면) continue;
        영역 개수 카운트
        현재 지점을 시작으로 dfs 실행
    }
}

 

 이제 dfs 함수를 설계해봅시다. dfs는 다음과 같은 형태로 구성할 수 있습니다.

1. 현재 지점 방문처리
2. 이동할 다음 지점 계산
3. 다음 지점에 방문할 수 있다면 방문

방문 처리는 visited 배열에 값을 대입하여 쉽게 해결할 수 있습니다. 다음 지점 계산 또한, 방향 배열을 활용하여 쉽게 계산할 수 있습니다.

 

 이 문제에서는 상하좌우 네 방향으로 탐색을 진행하므로 크기가 4인 방향 배열을 사용하면 됩니다. 이 문제에서는 탐색 순서가 중요하지 않기 때문에 네 방향만 탐색할 수 있다면 어떤 순서로 탐색해도 상관없습니다. 방향 배열은 아래와 같이 구성하면 됩니다.

인덱스 순서대로 상, 우, 좌, 하 방향입니다.
int dy[] = {-1, 0, 1, 0};
int dx[] = {0, 1, 0, -1};

 

 이동 지점 계산이 끝났으니 마지막으로 다음 지점이 방문가능한지를 판단해야 합니다. 가장 기본적으로 이미 방문한 지점인지와 배열 영역 밖으로 나가지 않았는지를 확인합니다. 이는 dfs를 사용한다면 반드시 있어야할 기본 확인 사항입니다.

 

 그 다음으로 확인해야할 것은 다음 지점이 배추가 있는 땅인지를 확인해야 합니다. 이 문제에서는 배추들의 연결 요소의 개수를 구하는 문제이므로 배추가 있는 지점에만 방문 체크를 해야하기 때문입니다.

 

 이를 종합하여 설계한 dfs함수는 다음과 같습니다.

void dfs(현재 위치){
    현재 위치 방문처리
    for(int i = 0; i < 4; i++){
        방향 배열을 통해 다음 위치 계산
        if(배열 영역 밖이라면) continue;
        if(이미 방문한 위치라면) continue;
        if(다음 위치가 배추라면) 다음 위치로 dfs 실행
    }
}

 

 지금까지 설계한 내용을 바탕으로 코드를 구성해봅시다.

---

알고리즘 구현하기

 최종적인 코드는 다음과 같습니다.

#include<iostream>
#include<queue>
#include<tuple>
#include<cstring>
using namespace std;

int t, m, n, k, x, y;
int a[50][50], visited[50][50];
/*방향 배열*/
int dy[4] = {-1 , 0, 1, 0};
int dx[4] = {0, 1, 0, -1};

void dfs(int y, int x){
    visited[y][x] = 1;
    for(int i = 0; i < 4; i++){
        int ny = y + dy[i];
        int nx = x + dx[i];
        if(ny < 0 || nx < 0 || ny >= n || nx >= m) continue; //out of bound 확인
        if(visited[ny][nx]) continue; //방문한 위치인지 확인
        if(a[ny][nx] == 1) //배추가 있는 위치인지 확인
            dfs(ny, nx);
    }
}

int main(){
	/*입출력 성능 향상*/
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> t;
    while(t--){
    	/*매 테스트 케이스마다 기본 정보 초기화*/
        memset(a, 0, sizeof(a));
        memset(visited, 0, sizeof(visited));
        
        cin >> m >> n >> k;
        for(int i = 0; i < k; i++){
            cin >> x >> y;
            a[y][x] = 1;
        }
        
        int cnt = 0; //연결 요소 개수
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
            	/*이미 방문했거나 배추가 아닌 영역은 탐색하지 않음*/
                if(a[i][j] == 0 || visited[i][j]) continue;
                cnt++;
                dfs(i, j);
            }
        }
        cout << cnt << '\n';
    }
    return 0;
}

 핵심 로직 부분에 대한 설명은 설계하기 단계에서 설명했으니 생략하도록 하겠습니다.

 

주의 사항 

 이 코드에서 로직만큼 중요한 부분은 바로 기본 정보 초기화 부분입니다.(while 루프 첫 두 줄) 이 문제와 같이 매 테스트케이스마다 독립적인 실행이 필요한 문제들은 반드시, 테스트케이스를 시작할 때나 끝날 때 이전 정보들을 초기화해야한다는 것에 주의해주세요!

 

 위 코드에서는 초기화를 <cstring>헤더의 memset 함수를 사용하여 초기화를 진행했는데, 이때, memset 함수는 1byte 단위로 초기화하기 때문에 -1, 0으로만 초기화 할때 사용할 수 있습니다.(char 타입도 가능합니다.) 만약, -1, 0이 아닌 다른 수로 초기화 해야하는 경우에는 fill 함수를 통해 초기화할 수 있습니다. 

---