1012-유기농배추

문제링크

NxN의 밭이 있는데, 배추가 있으면 1 없으면 0 을 할당.

배추 심어진 곳에 흰지렁이 두면 해충 방지 가능. 흰지렁이는 인접 배추로 이동할 수 있음(상하좌우)

배추 여러군데 퍼져있는데, 배추의 해충을 방지하기 위한 흰지렁이 최소 마리수 구하기.

DFS를 (0,0) ~ (N,N)까지 매번 호출 DFS

• base case

  • 경로 벗어나기

  • 이미 방문했을 경우

  • 배추가 없을 경우

• 배추가 있다면

  • 카운트 +1

  • 상하좌우 각각 DFS 수행.

하면 간단하게 풀림

int cnt;
int r, c, cabagge;

int direction[4][2] = {
    {-1, 0}, {0,1}, {1,0}, {0, -1}
};

bool isExistBug;


void goodBugDFS(
    int row, int col, int farm[][50], bool visited[][50]
) {
    if(row < 0 || row >= r || col < 0 || col >= c) {
        return;
    }
    if(visited[row][col]) {
        return;
    }
    visited[row][col] = true;

    if(farm[row][col] == 0) {
        return;
    }
    else {
        if(!isExistBug) {
            isExistBug = true;
            cnt += 1;
        }
    }

    for(int i = 0; i<4; i+=1) {
        goodBugDFS(row + direction[i][0], col + direction[i][1], farm, visited);
    }
}

int main(int argc, const char * argv[]) {

    int n;

    cin>>n;

    for(int i = 0; i<n; i++) {
        int farm[50][50];
        bool visited[50][50];

        cin>>r>>c>>cabagge;

        for (int k = 0; k<r; k+=1) {
            fill_n(farm[k], c, 0);
            fill_n(visited[k], c, false);
        }

        int row, col;
        for(int j = 0; j<cabagge; j+=1) {
            cin>>row>>col;
            farm[row][col] = 1;
        }

        for(int rr = 0; rr<r; rr+=1) {
            for(int cc = 0; cc<c; cc+=1) {
                isExistBug = false;
                goodBugDFS(rr,cc,farm, visited);
            }
        }


        cout<<cnt<<endl;

        cnt = 0;
    }

    return 0;
}

배운거

1차원 배열 값 초기화시, fill_n(주소, 길이, 초기화할 값) 2차원 배열 값 초기화시 for문으로 fill_n 각각 돌려줘야함.