[알고리즘] 인구 이동

포인트

• bfs 를 잘 구현을 할 수 있는가?
• 사이 값을 구할 수 있는가?
• 조건 대로 값을 잘 구해보자 문제를 잘 읽어보자

🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. 

#include <iostream>
#include <cstring>
#include <stack>
#include <tuple>
#include <queue>

using namespace std;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

int map[51][51];
int visited[51][51];
int n, l, r;

bool bfs() {
    memset(visited, 0, sizeof(visited)); //초기화
    bool flag = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (!visited[i][j]) {
                queue<pair<int, int>> q;
                q.push(make_pair(i, j));
                visited[i][j] = 1;
                vector<pair<int, int>> vc; // 국경 열리는 좌표 저장
                vc.push_back({i, j});

                while (!q.empty()) { //bfs
                    int x, y;
                    tie(x, y) = q.front();
                    q.pop();

                    for (int k = 0; k < 4; k++) {
                        int nx = x + dx[k];
                        int ny = y + dy[k];
                        if (0 > nx || nx >= n || 0 > ny || ny >= n) continue;
                        // 범위 체크
                        if (!visited[nx][ny]) {
                            int diff = abs(map[nx][ny] - map[x][y]); //차이를 구함
                            if (l <= diff && diff <= r) { // 차이가 조건 사이에 있으면
                                q.push(make_pair(nx, ny));
                                vc.push_back({nx, ny});
                                visited[nx][ny] = 1;
                                flag = 1;
                            }
                        }
                    }
                } // 탐색이 끝나면
                int sum = 0;
                for (auto ele :vc) sum += map[ele.first][ele.second];
                int value = sum / vc.size();
                for (auto ele : vc) map[ele.first][ele.second] = value; //map 을 값으로 변경
            }
        }
    }
    return flag;
}

int main() {
    cin >> n >> l >> r;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
        }
    } // 입력

    int answer = 0;
    while (1) { //반복
        if (bfs()) answer += 1; // 1씩 증가한다.
        else break;
    }

    cout << answer << '\n';

    return 0;
}

2021 03 14 수정

python

from collections import deque


n, l, r = map(int, input().split())

data = [list(map(int, input().split())) for _ in range(n)]
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]


def bfs() -> bool:
    flag = False # 국경이 열리지 않았다.
    visited = [[0] * n for _ in range(n)] # 방문 표시

    for i in range(n): # 방문 하지 않는 곳을 검사한다.
        for j in range(n):
            open = []

            if visited[i][j] == 0: # 방문하지 않았니까
                q = deque()
                q.append([i, j])
                visited[i][j] = 1
                open.append([i, j])

                while q: # BFS 검사
                    x, y = q.popleft()

                    for direction in range(4): # 4방향을 봐서
                        nx = x + dx[direction]
                        ny = y + dy[direction]

                        if not (0 <= nx < n and 0 <= ny < n): # 범위 제한
                            continue

                        if visited[nx][ny] == 0 and (l <= abs(data[nx][ny] - data[x][y]) <= r): # 범위 안에 드면
                            q.append([nx, ny])
                            visited[nx][ny] = 1
                            open.append([nx, ny]) # 국경이 열린곳 좌표 저장
                            flag = True

                summation = 0
                for x, y in open: # 국경이 열린곳 좌표 저장
                    summation += data[x][y]
                value = summation // len(open)
                for x, y in open:
                    data[x][y] = value

    return flag


answer = 0
while True:
    if bfs():
        answer += 1
    else:
        break

print(answer)