[백준] 1012 유기농 배추

문제 설명

오늘도 그래프 문제를 풀었다! 어제는 [백준] 11724 연결 요소의 개수 문제를 풀었다면 오늘은 이름만 바뀐 유기농 배추 문제이다! 처음에 슬쩍 보고는 bfs 문제인 줄 알았다. 토마토 문제처럼 배추가 다 익는데 얼마나 걸리냐! 를 묻는 문제인 줄 알았다. 그러나 이것도 마찬가지로 탐색을 통해서 몇 번의 그래프 탐색이 필요한지 (결국, 몇 마리의 벌레가 필요한지)를 묻는 문제이다. 따라서 풀이는 어제와 매우매우매우 흡사하다. 나도 푸는 데 어제는 힘들었는데 오늘은 안 힘들었다.

문제 링크 : 백준_1012_유기농_배추

풀이

이 문제도 어제의 11724 연결 요소의 개수 문제와 흡사하기 때문에, 풀이가 궁금하다면 이전 포스트를 보고 와도 좋겠다! 어제 설명 했듯, 이 문제는 탐색 방법을 어떤 걸 쓰냐가 중요한 게 아니라 그래프 탐색이 이루어지는 횟수를 세는 문제이기 때문에, dfs든 bfs든 어떤 탐색 방법을 써도 상관이 없다. 어제는 dfs, bfs 모두 설명 했지만 오늘은 dfs만을 이용해서 문제를 풀었다. (난 dfs를 먼저 공부해서 아직도 dfs가 더 편하다) 어제와 다르게 이번에는 인접 행렬을 써서 문제를 풀었다. 어제는 인접 리스트를 써서 벡터를 사용했지만, 오늘은 인접 행렬을 사용했기 때문에 벡터를 쓰지 않고 2차원 배열만을 이용해서 문제를 풀었다. 코드는 다음과 같다.

#include <cstdio>
#include <string.h>
using namespace std;

int n,m,k;
int adj[51][51];
bool v[51][51];

int dx[4]={-1, 0, 1, 0}; // 토마토 문제처럼 상, 하, 좌, 우로 벌레가 움직일 수 있다
int dy[4]={0, 1, 0, -1};

void dfs(int y, int x){
    v[y][x]=true;
    for(int i=0;i<4;i++){
        int nx=x+dx[i];
        int ny=y+dy[i];

        // 위치의 범위는 1~n이 아니라 0~n-1이다. 또한 인접 행렬을 사용했기 때문에 adj[ny][nx]=1인 것도 한번 더 따져 주어야 한다.
        if(nx>=0 && nx<m && ny>=0 && ny<n && adj[ny][nx]==1 && !v[ny][nx]){ 
            dfs(ny, nx);
        }
    }
}

int main(){
    int t;
    scanf("%d", &t);
    while(t--){
        memset(adj,0,sizeof(adj)); // string.h에 정의되어 있는 memset함수를 사용하면 2차원 행렬을 간단하게 초기화 해줄 수 있다.
        memset(v,0,sizeof(v)); // 위와 동일, 배열 초기화 시 많이 사용!

        scanf("%d%d%d", &m, &n, &k);
        int x, y;
        for(int i=0;i<k;i++){
            scanf("%d%d", &x, &y);
            adj[y][x]=1;
        }
        int cnt=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(!v[i][j] && adj[i][j]){
                    dfs(i, j);
                    cnt++;
                }
            }
        }
        printf("%d\n", cnt);
    }
}