백준 16234 : 인구 이동

문제 링크입니다 https://www.acmicpc.net/problem/16234

16234번: 인구 이동

1. 인구 이동이 가능한 나라들을 bfs를 통해 찾고 인구 이동을 시킨다.

   (단, 하루 동안 같은 나라가 두 번 인구 이동을 하지 않도록 주의한다)

 

2. 하루가 지났으면 인구 이동 횟수를 한 번 증가시키고 1번으로 돌아간다.

 

좀 더 구체적인 설명은 주석을 참고해주세요

 

 

[소스코드 + 주석]

 

// [백준] 삼성 SW 역량 테스트 기출 문제 : 인구 이동(16234)
 
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
const int MAX = 50 + 10;
 
struct p {    // 좌표를 저장하기 위한 구조체
    int y, x;
};
 
// 하루동안 인구 이동이 일어난 나라를 체크해줄 배열
// 같은 날 똑같은 나라가 두 번 인구 이동을 하면 안됨
bool visit[MAX][MAX];    
 
int n, L, R, ret, map[MAX][MAX], mapCopy[MAX][MAX];
 
const int dy[] = { -1, 0, 1, 0 };
const int dx[] = { 0, -1, 0, 1 };
 
// 좌표를 인자로 받아서 p type으로 바꿔주는 함수
p make_p(int y, int x) {
    p temp;
 
    temp.y = y, temp.x = x;
    return temp;
}
 
// 좌표를 인자로 받아서 그 나라부터 인구 이동이 일어날 수 있는 나라들을
// bfs를 통해 탐색하고 탐색이 끝나면 인구를 이동시켜주고 인구 이동이
// 일어났으면 true, 일어나지 않았으면 false를 반환하는 함수
bool bfs(int y, int x) {
    bool check[MAX][MAX] = { 0, };    // 인구 이동이 일어날 수 있는지 체크하는 배열
   queue <p> q;
 
    visit[y][x] = true;
    check[y][x] = true;
 
    q.push(make_p(y, x));
    int cnt = 1, sum = 0;
 
    bool flag = false;
    while (!q.empty()) {
        p cur = q.front();
        q.pop();
 
        // 인구 이동이 일어날 수 있는 나라만 Queue에 push하므로 현재 인구를
        // 누적하여 더해준다
        int current = map[cur.y][cur.x];
        sum += current;
 
        for (int i = 0; i < 4; i++) {
            int yy = cur.y + dy[i];
            int xx = cur.x + dx[i];
            
            int next = map[yy][xx];
 
            if (check[yy][xx] || yy < 0 || yy >= n || xx < 0 || xx >= n) continue;
 
            int temp = abs(next - current);
 
            // 다음칸의 인구와 내 인구의 차이가 L이상 R이하라면
            if (L <= temp && temp <= R) {
                cnt++;            // 나라의 수를 세어주고
                flag = true;     // 인구 이동이 일어났습니다
                visit[yy][xx] = true;
                check[yy][xx] = true;
                q.push(make_p(yy, xx));
            }
        }
    }
    if (flag) {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                // 인구 이동이 일어난 나라이면 값(인구수의 합 / 나라의 수)을 넣어준다
                if (check[i][j]) mapCopy[i][j] = sum / cnt;    
        return true;
    }
    else {
        // 인구 이동이 일어나지 않았으면 그 좌표는 미 방문 처리
        check[y][x] = false;
        visit[y][x] = false;
        return false;
    }
}
 
void solve(void) {
    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]);
            mapCopy[i][j] = map[i][j];    // 입력받은 땅 정보 복사
        }
    }
    while (1) {
        bool isUpdate = false;    // 인구 이동이 일어났냐
 
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (!visit[i][j])
                    if (bfs(i, j)) isUpdate = true;
 
        if (!isUpdate) break;    // 더 이상 인구 이동은 일어나지 않는다
        else {
            ret++;    // 인구 이동이 일어난 횟수 카운트
 
            // 하루가 지났으므로 visit 초기화 및 하루가 지난 map으로 update
            memset(visit, 0, sizeof(visit));
            memcpy(map, mapCopy, sizeof(mapCopy));
        }
    }
    printf("%d", ret);
}
 
int main(void) {
    solve();
    return 0;
}

 

 

[주석 없는 소스코드]

 

#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
const int MAX = 50 + 10;
 
struct p {
    int y, x;
};
bool visit[MAX][MAX];
int n, L, R, ret, map[MAX][MAX], mapCopy[MAX][MAX];
 
const int dy[] = { -1, 0, 1, 0 };
const int dx[] = { 0, -1, 0, 1 };
 
p make_p(int y, int x) {
    p temp;
 
    temp.y = y, temp.x = x;
    return temp;
}
 
bool bfs(int y, int x) {
    bool check[MAX][MAX] = { 0, };
   queue <p> q;
 
    visit[y][x] = true;
    check[y][x] = true;
 
    q.push(make_p(y, x));
    int cnt = 1, sum = 0;
 
    bool flag = false;
    while (!q.empty()) {
        p cur = q.front();
        q.pop();
 
        int current = map[cur.y][cur.x];
        sum += current;
 
        for (int i = 0; i < 4; i++) {
            int yy = cur.y + dy[i];
            int xx = cur.x + dx[i];
            
            int next = map[yy][xx];
 
            if (check[yy][xx] || yy < 0 || yy >= n || xx < 0 || xx >= n) continue;
 
            int temp = abs(next - current);
            if (L <= temp && temp <= R) {
                cnt++;
                flag = true;
                visit[yy][xx] = true;
                check[yy][xx] = true;
                q.push(make_p(yy, xx));
            }
        }
    }
    if (flag) {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (check[i][j]) mapCopy[i][j] = sum / cnt;
        return true;
    }
    else {
        check[y][x] = false;
        visit[y][x] = false;
        return false;
    }
}
 
void solve(void) {
    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]);
            mapCopy[i][j] = map[i][j];
        }
    }
    while (1) {
        bool isUpdate = false;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (!visit[i][j])
                    if (bfs(i, j)) isUpdate = true;
 
        if (!isUpdate) break;
        else {
            ret++;
            memset(visit, 0, sizeof(visit));
            memcpy(map, mapCopy, sizeof(mapCopy));
        }
    }
    printf("%d", ret);
}
 
int main(void) {
    solve();
    return 0;
}