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

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

1012번: 유기농 배추

그래프가 주어져있고, 그 주변을 상하좌우로 탐색해나가고 싶을때는 웬만하면 dfs이다.

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

int M, N, K;
bool visited[50][50] = {false,};
int table[50][50] = {0,};
int dy[4] = {1, -1, 0, 0};
int dx[4] = {0, 0, 1, -1}; //상하좌우 로직은웬만하면 이런식으로 설정한다.

void dfs(int y, int x)
{
    for(int i = 0; i < 4; i++)//모든 상하좌우에 조건에 만족하는 값이 없을때까지 재귀를 반복하며 for문 실행
    {
        int ny = y + dy[i];
        int nx = x + dx[i];//진입하자마자 상하좌우로 좌표하나 이동하고 시작
        if(ny < 0 || ny >= N || nx < 0 || nx >=M)
            continue; //좌표 범위를 벗어난 경우는 아래 if문 실행하지 않고 다음 for문 돌기
        if(table[ny][nx] && !visited[ny][nx])//상하좌우에 위치해있는곳이 적절한 조건 갖췄을 때
        {
            visited[ny][nx] = true; //해당하는 좌표도 visited 를 true로 바꿔주고
            dfs(ny, nx); //새로 할당된 좌표에서 다시 깊이우선탐색 실행
        }
    }
}


int main()
{
    int jirong,T;
    cin >> T;
    while(T--)
    {
        jirong = 0;
        memset(table, 0, sizeof(table));
        memset(visited, false, sizeof(visited));//memset(배열, 초기값, sizeof(배열)) :초기화
        cin >> M >> N >> K;
        while(K--)
        {
            int x,y;
            cin >> x >> y;
            table[y][x] = 1;
        }//테이블 세팅
        for(int i = 0; i < N; i++) // x, y, M , N 어떤 값 들어갈지 조건 잘 보기
        {
            for(int j = 0; j < M; j++) //요소를 하나하나 돌되, 
            {
                if(table[i][j] && !visited[i][j]){ //깊이우선탐색 실행을 시작해야하는 경우
                    jirong++;
                    visited[i][j] = true; // 이 경우에 답을 하나 증가시키고 이 부부은 방문한것으로 표시
                    dfs(i,j);//현재 좌표를 넣고 dfs에 진입 시에는 for문으로 현 좌표에서의 상하좌우부터 돌린다.
                }
            }
        }
        cout << jirong << endl;
    }
    return 0;
}