[BaekJoon/백준] 1012번 C++

VISITED 배열을 따로 구현하신 분들이 많았는데,

이 문제에서는 딱히 구현해줄 필요 없이 기존 배열을 활용하여 VISITED 기능을 사용할 수 있다.

#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;

int T; // 테스트 케이스
int arr[50][50]; // 논밭 최대 크기
int N, M; // 가로, 세로

int C; // 배추 수
int x, y; // 배추 위치를 위해

int total; // 전체 지렁이 갯수


// 인근 1 영역을 모두 0으로 만들어주는 함수. (재귀)
void road(int x, int y) {
    
    if(arr[x][y] == 1)
        arr[x][y] = 0;
    else
        return;
    
    if(x - 1 >= 0)
        road(x - 1, y);
    if(x + 1 <= N - 1)
        road(x + 1, y);
    if(y - 1 >= 0)
        road(x, y - 1);
    if(y + 1 <= M - 1)
        road(x, y + 1);
    
    
}


int main() {

    scanf("%d", &T);
    
    while(T--) {
        total = 0;
        scanf("%d %d %d", &N, &M, &C);
        
        while(C--) {
            scanf("%d %d", &x, &y);
            arr[x][y] = 1;
        }
        
        // 각 요소를 돌면서, 1인 경우에 road()재귀를 수행해서 인근 영역을 모두 0으로 만들어줌.
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++) {
                
                // (0,0)이 1이고 (0,1)도 1이라고 봤을 때
                // (0,0)에서 if문이 시행되어 road() 재귀로 인해 (0,1)을 이미 0으로 만들어주었기에
                // 반복문에서 i = 0, j = 1이 왔을 때에 이 if문이 시행되지 않는 것.
                // 즉, 1이라면 해당자리에서 재귀 시작하여 조건상 인접의 모든 영역의 1을 0으로 처리해준 뒤 지렁이 하나 증가시키는 결과.
                if(arr[i][j] == 1) {
                    total++;
                    road(i, j);
                }
            }
        }
        printf("%d\n", total);
    }
}

 

그리고 이 문제에는 가지치기가 존재하기에 백트래킹이라고 보는 것이 맞다고 생각하는데

dfs라고 설명하시는 분들이 정말 많았다. (백준 카테고리도 dfs에 올려져있고..)

 

물론 깊이 우선 탐색이라는 의미에서는 맞긴 한데...

 

근데 두 개념이 워낙에 구분없이 혼용해서 쓰이기도 한다.

 

문제 풀이에 있어서는 이러한게 중요하지도 않지만.. 그냥 궁금해서 관련 질문을 백준에 올려봤다.

www.acmicpc.net/board/view/66010