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

https://www.acmicpc.net/problem/1012

1012번: 유기농 배추

---

#include <iostream>
#include <vector>
using namespace std;

int M,N,K;
int map[50][50];
bool visited[50][50];
int dir[4][2] = {{1,0},{-1,0},{0,-1},{0,1}};

void reset()
{
    for(int y = 0;y<N;y++)
        for(int x = 0;x<M;x++)
        {
            map[y][x] = 0;
            visited[y][x] = 0;
        }
}

void DFS(int y, int x)
{
    visited[y][x] = true;
    
    for(int d = 0;d<4;d++)
    {
        int ny = y+dir[d][0];
        int nx = x+dir[d][1];
                         
        if(( ny >= 0 && nx >= 0) && (ny < N && nx < M))
        {
            if(map[ny][nx] == 1 && !visited[ny][nx])
            {
                visited[ny][nx] = true;
                DFS(ny, nx);
            }
        }
    }
}

int main()
{
    int T;
    cin>>T;
    
    for(int i = 0 ;i<T;i++)
    {
        cin >> M >> N >> K;
        reset();
        for(int k = 0;k<K;k++)
        {
            int x,y;
            cin>>x>>y;
            map[y][x] = 1;
        }
        
        int result = 0;
        for(int y = 0;y<N;y++)
        {
            for(int x = 0; x<M;x++)
            {
                if(!visited[y][x] && map[y][x]==1)
                {
                    DFS(y,x);
                    result++;
                }
            }
        }
        cout<<result<<endl;
    }
}

BFS로 풀었던 문제를 DFS로 다시 풀어보았다.

큐와 while문을 통해 반복해주었던 부분을 재귀적으로 바꾸어 해결했다.

 

처음에는 for문의 위치를 잘못 배치해서 틀렸었다!!!