[DFS] 인구 이동 - 백준 16234번

16234번: 인구 이동

첫번째 풀이 (실패)

위 그림 처럼 구간을 나누려고 했음

그래서 기존의 2중 vector A와 2중 vector B를 만들어 구간을 1로 만드는 작업을 수행

이렇게 말이다. 하지만 반례가 발생!!

반례

서로 다른 구간이 겹쳐지는 문제 발생

두번째 풀이 (실수)

if(abs(A[x][y] - A[x+dx[i]][y+dy[i]]) >= L && abs(A[x][y] - A[x+dx[i]][y+dy[i]]) <= R) {
    sum += A[x][y];
    cnt++;
    lst.push_back(make_pair(x+dx[i], y+dy[i]));
    visited[x][y] = -1;
    func(x+dx[i], y+dy[i]);
}

A[x][y]이 조건에 충족한다면 sum에 추가하여 누적

하지만 마지막 칸이 sum에 누적되지 않는다!!

마지막 풀이 (성공)

void func(int x, int y) {
    visited[x][y] = 1;
    sum += A[x][y];
    cnt++;
    lst.push_back(make_pair(x, y));

함수 들어오자마자 그냥 push & sum 에도 추가

조건에 맞지 않는 셀도 들어가지 않냐??!!

if(cnt > 1) { // cnt 자기 빼고 2이상
    movement = true;
    int newPopulation = sum / cnt;
    for(int k=0; k<lst.size(); k++) {
        A[lst[k].first][lst[k].second] = newPopulation;
    }
}

그래서 cnt를 2이상으로 올린다.

자기 빼고 한개 더 ⇒ 인접한 셀이 있다!

코드

https://github.com/KimGyeongLock/CodingTest/blob/main/16234.cpp