[백준 1012] 유기농 배추

유기농 배추 (DFS)

문제설명

dfs알고리즘을 사용한 문제로 노드간의 연결된 관계를 파악하여 그 갯수를 세는 문제이다.

알고리즘 순서

1. 테스트케이스(T)와 밭의 가로세로 크기(M,N), 간선의 갯수(K)를 입력 받는다.
2. 연결관계를 2차원 graph에 1로 표현한다. 예) 2,3 -> graph[2][3]=1
3. graph를 반복해서 연결관계가 1이고 현재 방문하지 않은 노드를 방문한다.
4. dfs함수에서 방문했다는 visited[x][y]=1 표현으로 방문 여부를 체크하고 현재 노드에서 상,하,좌,우 연결관계를 재귀적으로 확인한다.
5. 재귀적인 확인을 마친뒤 다시 main 함수로 돌아오면 answer값을 증가시킨다.
6. 여러번 테스트를 위해서 vector에 값을 담아 놓았다.

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <vector>
using namespace std;
#define MAX 51

int graph[MAX][MAX];
int T,M,N,K;
bool visited[MAX][MAX];
void DFS(int x,int y)
{
    visited[x][y] = 1;

    if (graph[x + 1][y] == 1 && visited[x + 1][y] == 0)//현재 방문한 노드의 오른쪽이 방문 가능하고 아직 가지 않은 경우
        DFS(x + 1, y);
    if (graph[x-1][y] == 1 && visited[x -1][y] == 0)//현재 방문한 노드의 왼쪽이 방문 가능하고 아직 가지 않은 경우
        DFS(x - 1, y);
    if (graph[x][y+1] == 1 && visited[x][y+1] == 0)//현재 방문한 노드의 아래쪽이 방문 가능하고 아직 가지 않은 경우
        DFS(x , y+1);
    if (graph[x][y-1] == 1 && visited[x ][y-1] == 0)//현재 방문한 노드의 위쪽이 방문 가능하고 아직 가지 않은 경우
        DFS(x , y-1);
}

int main(void)
{
    cin >> T;
    int x, y;
    vector <int> v;

    while (T)//테스트 케이스 반복을 위함 
    {
        cin>> M >> N >> K;
        int answer = 0;
        for (int i = 0; i < K; i++)//연결 관계 입력 받기
        {
            cin >> x >> y;
            graph[x][y] = 1;
        }

        for (int i = 0; i < M; i++)
        {
            for (int j = 0; j < N; j++)
            {
                if (graph[i][j] == 1 && visited[i][j] == 0)//연결되어있으며 방문하지 않은 노드 방문
                {
                    DFS(i, j);//함수 실행
                    answer++;//방문 후 구역 계산 
                }
            }
        }
        T--;
        v.push_back(answer);//정답 저장
        fill(&graph[0][0], &graph[MAX - 1][MAX], 0);//다음 테스트를 위한 초기화
        fill(&visited[0][0], &visited[MAX - 1][MAX], 0);
    }
    for (int i = 0; i < v.size(); i++)//정답 출력 
        cout << v[i] << endl;
    return 0;
}

DFS 알고리즘

1. 재귀적으로 연결된 노드 방문
2. stack stl을 사용하여 반복문을 통해서 방문 가능