[BOJ:16234] 인구 이동

문제

https://www.acmicpc.net/problem/16234

[

16234번: 인구 이동

N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모

www.acmicpc.net

](https://www.acmicpc.net/problem/16234)

코드

//https://www.acmicpc.net/problem/16234
//DFS 풀이, 인구 총합을 return 값으로 반환하도록 풀이
#include <stdio.h>
#include <algorithm>
int n, l, r, cnt;
int map[50][50];
int visited[50][50];
int dirR[] = { -1,1,0,0 };
int dirC[] = { 0,0,-1,1 };

int allyPeople(int row, int column, int preValue) {
    if (row < 0 || row > n - 1 || column < 0 || column > n - 1) return 0;
    if (visited[row][column]) return 0;
    //main에서 preValue = -1로 처리한 시작 위치가 넘어오면 이전 값이 없기 때문에 차이를 구할 게 없음  
    if (preValue != -1) {
        int delta = abs(preValue - map[row][column]);
        if (delta<l || delta>r) return 0;
    }
    visited[row][column] = 1;
    ++cnt;

    int sum = map[row][column];
   /* for (int dir = 0; dir < 4; ++dir) {
        int nr = r + dirR[dir];
        int nc = c + dirC[dir];
        sum += totalAllyPeople(nr, nc, map[r][c]);
    }*/

     sum += allyPeople(row-1,column,map[row][column]); //각 위치에서 상하좌우 끝내고 리턴
     sum += allyPeople(row+1,column,map[row][column]);
     sum += allyPeople(row,column-1,map[row][column]);
     sum += allyPeople(row,column+1,map[row][column]);

    return sum;
}
void renewal(int row, int column, int avg) {
    if (row < 0 || row > n - 1 || column < 0 || column > n - 1) return;
    if (visited[row][column] != 1) return;
    visited[row][column] = 2;

    map[row][column] = avg;

    /*for (int dir = 0; dir < 4; ++dir) {
        int nr = r + dirR[dir];
        int nc = c + dirC[dir];
        renewal(nr, nc, avg);
    }*/

    renewal(row-1,column,avg);
    renewal(row+1,column,avg);
    renewal(row,column-1,avg);
    renewal(row,column+1,avg);

}

int go() {
    int answer = 0;
    bool flag;

    do {
        flag = false;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                visited[i][j] = 0;
            }
        }

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (visited[i][j] == 0) { //방문만 했으면 1, 인구수 갱신국이면 2
                    cnt = 0;
                    int total = allyPeople(i, j, -1);
                    if (cnt > 1) { //cnt가 1이면 자기 혼자만 동맹국
                        flag = true;
                        renewal(i, j, total / cnt);
                    }
                    else {
                        visited[i][j] = 2;
                    }
                }
            }
        }

        if (flag) ++answer;
    } while (flag);

    return answer;
}

int main() {
    freopen("input.txt", "rt", stdin);
    scanf("%d %d %d", &n, &l, &r);

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            scanf("%d", &map[i][j]);
        }
    }
    printf("%d", go());

    return 0;
}

BFS로 구현 풀이, 구조체로 position 잡아서
#include <stdio.h>
#include <algorithm>
#include <queue>
using namespace std;

typedef struct position{
    int r, c;
}POSI;

int n, l, r;
int map[50][50];

void check_area(int sr, int sc, int area[][50],int index, int& count, int& sum) {
/*
다른 시작점에서는 동맹국이 아닐지 모르지만 지금 시작점에서 다시 동맹국으로 생길지 모르기 때문에 
main for문에서 매번 시작좌표로 함수를 호출할때 마다 모든 좌표 방문은 초기화 해주어 현재 시작 위치로부터 방문 했었은지 확인해야 한다.
*/
    int visited[50][50] = { 0, }; 

    const int dr[] = { -1, 1, 0, 0 };
    const int dc[] = { 0, 0, -1, 1 };

    //탐색진행 전 start row, start coloum을 큐에 넣기 작업
    queue<POSI> q; //구조체를 통해 생성한 사용자 정의형 타입, POSI라는 타입을 담을 수 있는 큐
    POSI head; //head에는 int r,int c가 쌍으로 있는 타입 POSI타입의 head라는 변수명을 가진 변수 선언 
    head.r = sr;
    head.c = sc;
    visited[sr][sc] = 1;
    q.push(head);

    while (!q.empty()) {
        POSI cur = q.front(); //큐에 제일 앞에 있는 POSI 타입 변수 반환
        q.pop();

        area[cur.r][cur.c] = index;
        ++count;
        sum += map[cur.r][cur.c];
        //현재 위치(r,c)에서 문제의 조건에 부합하는 상하좌우에 위치한 곳은 전부 큐에 넣기
        for (int dir = 0; dir < 4; ++dir) {
            POSI next;
            next.r = cur.r + dr[dir];
            next.c = cur.c + dc[dir];

            if (next.r < 0 || next.r >= n || next.c < 0 || next.c >= n) continue; //주어진 map에서 벗어난 위치이면 다음 방향 찾기

            int delta = abs(map[cur.r][cur.c] - map[next.r][next.c]); //절대값 차 구하기
            if (visited[next.r][next.c] == 0 && l <= delta && delta <= r) {
                visited[next.r][next.c] = 1;
                q.push(next);
            }
        }
    }
}


int main(){
    freopen("input.txt", "rt", stdin);

    scanf("%d %d %d", &n, &l, &r);
    for (int y = 0; y < n; ++y) {
        for (int x = 0; x < n; ++x) {
            scanf("%d", &map[y][x]);
        }
    }

    int result = 0;
    bool is_update = true;
    while (is_update) {
        is_update = false;

        int what_area[50][50] = { 0, };
        int area_index = 0;
        int area_count[2501] = { 0, };//50*50 = 2500개의 개별 국가 존재 가능
        int people_sum[2501] = { 0, };
        for (int r = 0; r < n; ++r) {
            for (int c = 0; c < n; ++c) {
                if (what_area[r][c] == 0) {
                    ++area_index;
                    check_area(r, c, what_area, area_index, area_count[area_index], people_sum[area_index]);
                }
            }
        }

        for (int r = 0; r < n; ++r) {
            for (int c = 0; c < n; ++c) {
                int area_num = what_area[r][c];
                int avg = people_sum[area_num] / area_count[area_num];
                if (map[r][c] != avg) {
                    map[r][c] = avg;
                    is_update = true;
                }
            }
        }
        if (is_update) {
            ++result;
        }
    }

    printf("%d\n", result);
    return 0;
}

#include <stdio.h>
#include <queue>
#include <algorithm>
using namespace std;
struct POSI {
    int rr, cc;
};
int map[50][50];
int check[50][50];
int n, l, r;
int sum, cnt;
int dr[] = { -1,1,0,0 };
int dc[] = { 0,0,-1,1 };
bool isUpdate;

void go(int row, int column) {
    queue<POSI> q;
    queue<POSI> s;
    POSI head;
    head.rr = row;
    head.cc = column;


    q.push(head);

    while (!q.empty()) {
        POSI cur = q.front();
        q.pop();

        POSI nw;

        for (int dir = 0; dir < 4; ++dir) {
            nw.rr = cur.rr + dr[dir];
            nw.cc = cur.cc + dc[dir];

            if (nw.rr < 0 || nw.rr >= n || nw.cc < 0 || nw.cc >= n)continue;
            if (check[nw.rr][nw.cc])continue;
            int delta = abs(map[nw.rr][nw.cc] - map[cur.rr][cur.cc]);
            if (delta <l || delta>r)continue;
            //여기까지 통과했으면 동맹국 존재


            if (cnt == 0) {
                check[cur.rr][cur.cc] = 1;
                sum += map[cur.rr][cur.cc];
                ++cnt;
                s.push(cur);
            }

            check[nw.rr][nw.cc] = 1;
            sum += map[nw.rr][nw.cc];
            ++cnt;

            q.push(nw);
            s.push(nw);

        }
    }

    if (!s.empty()) isUpdate = true;

    while (!s.empty()) {
        POSI ch = s.front();
        s.pop();
        map[ch.rr][ch.cc] = (sum / cnt);
        check[ch.rr][ch.cc] = 2;
    }
}

void renewal(int row, int column, int avg) {

    queue<POSI> q;
    POSI head;
    head.rr = row;
    head.cc = column;
    q.push(head);

    while (!q.empty()) {
        POSI cur = q.front();
        q.pop();
        check[cur.rr][cur.cc] = 2;
        map[cur.rr][cur.cc] = avg;
        POSI nw;

        for (int dir = 0; dir < 4; ++dir) {

            nw.rr = cur.rr + dr[dir];
            nw.cc = cur.cc + dc[dir];
            if (nw.rr < 0 || nw.rr >= n || nw.cc < 0 || nw.cc >= n)continue;

            if (check[nw.rr][nw.cc] == 1) {
                q.push(nw);
            }
        }

    }

}

int main() {
    int answer = 0;
    freopen("input.txt", "rt", stdin);

    scanf("%d %d %d", &n, &l, &r);

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            scanf("%d ", &map[i][j]);
        }
    }

    do {
        isUpdate = false;

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (check[i][j] == 0) {
                    sum = cnt = 0;
                    go(i, j);
                }
            }
        }

        if (isUpdate) {
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < n; ++j) {
                    check[i][j] = 0;
                }
            }
            ++answer;
        }

    } while (isUpdate);

    printf("%d", answer);

    return 0;
}

문제해결방법

• 첫 번째 풀이

  • DFS로 풀이했다.
  • main에서 do while 문으로 일단 한번 동맹국 갱신이 있는지 체크를 먼저 시작하고 없었다면 while문을 종료하고 있었다면 다시 갱신하고 초기화 세팅을 하고 다시 다음 동맹국을 찾는 기본구조를 완성하고 갱신이 완료되면 갱신횟수를 증가시키는 코드를 구성하고 동맹국을 찾고 갱신하는 세부 알고리즘은 아래와 같다.
  • go 함수로 좌표값과 이전 위치에 인구값을 넘겨주면 해당 좌표와 인구의 차를 비교하여 인구차이가 문제의 주어진 범위 l과 r사이에 있는지를 체크하고 해당 조건에 맞는 다면 다음 상하좌우를 체크하기 위해 재귀호출을 진행한다. 이렇게 탐색을 진행하다가 문제의 조건에 벗어난 위치를 가거나 이미 방문했거나 인구차가 l과 r사이를 벗어 나는 곳이 발생한다면 반환한다.
  • 이때 인구조건에 맞는 곳을 체크만하고 다시 누적합을 구하기 위해 다른 함수를 호출하여 같은 작업을 반복하면 시간복잡도가 증가하기 때문에 동맹국을 확인하면서 동시에 누적합을 구하도록 구현하였다.
  • main에서 for문에서 동맹국을 확인하러 가기 시작하는 첫 위치를 출발할때는 sum과 cnt값은 초기화를 해주어 매번 새롭게 동맹국의 인구수 누적합과 동맹국수를 구할 수 있도록 했다.

• 두 번째 풀이

  • 위에서 풀이한 DFS를 BFS로 구현에 집중한 풀이를 구현했다. 동맹국을 스택 대신에 큐에 담아서 풀이했다.
  • 두개의 큐를 사용했는데 하나의 큐는 다음에 탐색할 동맹국을 저장해두는 역할 이고 이렇게 동맹국을 찾을 때마다 또 다른 큐에도 동시에 저장해두어 동맹국을 모두 찾은 후 인구수를 갱신할 때 활용했다. 갱신과정도 BFS탐색을 하며 풀이했다.