인구 이동문제 로직 의문점

작성한 질문수 8

0

안녕하세요 석기님 ㅎㅎ

그럴려면 먼저 dfs로 모든곳을 전부 순회한뒤에 구한 연합국의 인구수 / 연합국의 개수로 최종적으로 계산을 해줘야 할것같은데

>> 네 맞습니다. 그런 방식으로 코드가 진행되고 있습니다.

dfs -> dfs -> dfs -> dfs

로 만약 4개의 영역이 인구이동이 일어나면.

그 이후에 최종적으로 계산하고 있습니다.

void dfs(int y,int x,vector<pair<int,int>> &v){ 
    for(int i=0; i<4; i++){
        int ny = y+dy[i];
        int nx = x+dx[i];
        if(nx<0 || nx>=n || ny<0 || ny>=n || visited[ny][nx])continue;
        if(abs(a[ny][nx]- a[y][x]) >= l && abs(a[ny][nx] - a[y][x]) <= r){
            visited[ny][nx] =1;
            v.push_back({ny,nx});
            sum += a[ny][nx];
            dfs(ny,nx,v);

조건에 맞으면 dfs 호출.

그리고 그 이후에 dfs호출하면서 만들어놓은 vector v, sum을 기반으로

                    dfs(i,j,v);
                    if(v.size() == 1) continue;  
                    for(pair<int,int> b : v){ 
                        a[b.first][b.second] = sum / v.size();
                        flag = 1;
                    }

이 로직을 수행하며

순회한 연합국의 인구수 / 연합국의 개수

를 하는 것이죠. ㅎㅎ

정답코드 같은경우 커넥티드 컴포넌트에 해당되면 해당 컴포넌트 내에서 sum / v.size() 를 해주더군요 이렇게 되면 중간에 구해진 sum(인구수) v.size() (연합국의 개수) 로 구해지기 때문에 그다음 커넥티드 컴포넌트와 이전의 커넥티드 컴포넌트의 값이 다르게 되지 않나요?

>> 어차피 이동한 컴포넌트의 경우 visited 처리가 되기 때문에 영향을 받지 않습니다.

예를 들어.

1 2 3 4 5 6 이라는 컴포넌트가 있고.

1 2 3 4 5 6

여기까지 탐색을 완료했다면 1 2 3 4의 값은 변경됩니다. 그리고 그 이후 5에서 탐색할 때 4라는 정점은 건들지 않게 됩니다. 이미 visited가 되어있기 때문입니다.

그래서. 그 다음은. 이런식으로 탐색이 일어나게 되는 것이죠. ㅎㅎ

1 2 3 4 5 6

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.