Beakjoon 1012 유기농 배추

09 Jan 2021 in Algorithm

문제 링크 : https://www.acmicpc.net/problem/1012

나의 풀이

이 문제는 DFS, BFS로 해결이 가능하다. 배추가 있는 땅을 기준으로 아직 방문하지 않은 4방향으로 추적하면 하나의 구역을 얻을 수 있다. 이 때 배추가 없는 땅은 이미 방문했다고 생각하여 visit=1로 하였다. 이 과정을 반복하면 몇개의 구역이 있는지 구할 수 있다.

풀이 코드 : 1012 유기농 배추

#include <stdio.h>
#include <vector>
#include <string.h>

using namespace std;

int map[50][50];
int visit[50][50];

void dfs(int start_x, int start_y){
    vector<pair<int, int>> stack;
    stack.push_back(make_pair(start_x, start_y));
    int x,y;
    while(!stack.empty()){
        pair<int,int> curr = stack.back();
        x = curr.first;
        y = curr.second;
        visit[y][x] = 1;      
        stack.pop_back();
        if(x-1 >= 0 && visit[y][x-1] == 0 && map[y][x-1] == 1 ){
            stack.push_back(make_pair(x-1, y));
        }
        if(x+1 < 50 &&  visit[y][x+1] == 0 && map[y][x+1] == 1){
            stack.push_back(make_pair(x+1, y));
        }
        if(y-1 >= 0 && visit[y-1][x] == 0 && map[y-1][x] == 1 ){
            stack.push_back(make_pair(x, y-1));
        }
        if(y+1 < 50 &&  visit[y+1][x] == 0 && map[y+1][x] == 1){
            stack.push_back(make_pair(x, y+1));
        }
    }
}

int main(){
    int T, M, N, K, x, y;
    
    scanf("%d",&T);
    for(int t=0;t<T;t++){
        for(int i = 0;i<50;i++){
            memset(map[i], 0, sizeof(int)*50);
            memset(visit[i], 1, sizeof(int)*50);
        }
        scanf("%d %d %d",&M, &N, &K);
        for(int k = 0;k<K;k++){
            scanf("%d %d", &x, &y);
            visit[y][x] = 0;
            map[y][x] = 1;
        }

        int count = 0;
        for(int i = 0;i<N;i++){
            for(int j=0;j<M;j++){
                if(visit[i][j] == 0) {
                    dfs(j, i);
                    count++;
                }
            }
        }
        printf("%d\n", count);
    }
}

채점결과