백준 16234번 인구 이동

문제

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

코드

cpp

#include <vector>
#include <iostream>
#include<queue>
#include<string>
#include<map>
using namespace std;

int abs(int n) {
	if (n >= 0) return n;
	else return -n;
}

int main() {
	int answer = 0;
	int n, l, r;
	cin >> n >> l >> r;

	vector<vector<int>> map1(n, vector<int>(n, 0));
	

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++)
			cin >> map1[i][j];
	}

	
	int count = 1;
	int dir[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };

	while (1) {
		vector<vector<int>> map2(n, vector<int>(n, 0));
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (map2[i][j] != 0) continue;
				queue<pair<int, int>> q;
				q.push({ i,j });
				
				while (!q.empty()) {
					
					int y = q.front().first;
					int x = q.front().second;
					q.pop();

					for (int k = 0; k < 4; k++) {
						int new_y = y + dir[k][0];
						int new_x = x + dir[k][1];
						if (0 > new_y || new_y >= n || 0 > new_x || new_x >= n) continue;
						if (map2[new_y][new_x] != 0 ||
							l > abs(map1[y][x] - map1[new_y][new_x]) ||
							r < abs(map1[y][x] - map1[new_y][new_x])) continue;
						
						map2[y][x] = count;
						map2[new_y][new_x] = count;
						q.push({ new_y,new_x });
					}
				}
				count++;
			}				
		}
		// ----------인구이동이 있는지 검사
		bool result = true;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {

				if (map2[i][j] != 0) {
					result = false;
				}
			}	
		}
		if (result) break; //만약 없다면 while문 종료
		
		answer++; 
		map<int, pair<int, int>> hash;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				hash[map2[i][j]].first += map1[i][j];
				hash[map2[i][j]].second++;
			}
		}
		vector<pair<int, int>> list;
		for (auto i : hash) {
			if (i.first == 0) continue;
			list.push_back({ i.first,i.second.first / i.second.second });
		}
		for (int i = 0; i < list.size(); i++) {
			for (int j = 0; j < n; j++) {
				for (int k = 0; k < n; k++) {
					if (map2[j][k] == list[i].first)
						map1[j][k] = list[i].second;
				}
			}
		}

	}

	cout << answer;
}

python

from collections import deque


def bfs(num, i, j):
    q = deque()
    q.append((i, j))

    cnt = 1
    sum_v = board[i][j]

    while q:
        y, x = q.popleft()

        for dy, dx in d:
            newy = y+dy
            newx = x+dx
            if newy >= n or newy < 0 or newx >= n or newx < 0 or temp[newy][newx] != -1:
                continue

            if l <= abs(board[newy][newx]-board[y][x]) <= r:
                temp[newy][newx] = num
                sum_v += board[newy][newx]
                cnt += 1
                q.append((newy, newx))
    return cnt, sum_v


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

board = [list(map(int, input().split())) for _ in range(n)]

d = [[0, 1], [0, -1], [1, 0], [-1, 0]]


answer = 0

isTrans = True

while isTrans:
    isTrans = False
    lis = []
    num = 0
    temp = [[-1]*n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if temp[i][j] != -1:
                continue

            temp[i][j] = num
            cnt, sum_v = bfs(num, i, j)
            lis.append(sum_v//cnt)

            num += 1

            if cnt != 1:
                isTrans = True

    for i in range(n):
        for j in range(n):
            board[i][j] = lis[temp[i][j]]

    answer += 1

print(answer-1)

풀이

시뮬레이션 구현 문제에 bfs 한스푼 얹은 느낌의 문제네요 로직을 설명해보겠습니다

인구 이동이 없을때까지 반복하기 때문에 while문안에 코드를 작성하고 한번의 반복문마다 인구 이동이 있었는지 검사를 합니다 만약 이번 턴에 한번도 인구이동이 없다면 break문으로 나옵니다

​

N*N크기의 땅을 이차원 배열에 저장을 해둡니다 동시에 똑같은 크기의 이차원 배열을 0으로 채워서 만들어 놓고 연합을 이루는 땅들을 표시해줍니다

예를 들어 입력이

2 20 50
20 100
50 140

일 경우 map1은

map2는

이렇게 입력이 됩니다.

이중for문으로 map1의 모든요소를 처음부터 bfs를 사용해서 조건에 맞는 영역을 찾아서 연합을 표시해줍니다 만약 map2의 값이 0이 아니라면 이미 연합이 있는것이기 때문에 넘겨줍니다.

이중for문을 나오면 map2는

이렇게 영역이 구분됩니다.

그 뒤에 hashtable을 사용해서 평균값을 구해주고 대입을 해주면 됩니다