176. 인구 이동
1. Python
BFS
from collections import deque
# 땅의 크기(N), L, R 값을 입력받기
n, l, r = map(int, input().split())
# 전체 나라의 정보(N x N)를 입력 받기
graph = []
for _ in range(n):
graph.append(list(map(int, input().split())))
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
# 특정 위치에서 출발하여 모든 연합을 체크한 뒤에 데이터 갱신
def process(x, y, index):
# (x, y)의 위치와 연결된 나라(연합) 정보를 담는 리스트
united = []
united.append((x, y))
# 너비 우선 탐색 (BFS)을 위한 큐 라이브러리 사용
q = deque()
q.append((x, y))
union[x][y] = index # 현재 연합의 번호 할당
summary = graph[x][y] # 현재 연합의 전체 인구 수
count = 1 # 현재 연합의 국가 수
# 큐가 빌 때까지 반복(BFS)
while q:
x, y = q.popleft()
# 현재 위치에서 4가지 방향을 확인하며
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
# 바로 옆에 있는 나라를 확인하여
if 0 <= nx < n and 0 <= ny < n and union[nx][ny] == -1:
# 옆에 있는 나라와 인구 차이가 L명 이상, R명 이하라면
if l <= abs(graph[nx][ny] - graph[x][y]) <= r:
q.append((nx, ny))
# 연합에 추가하기
union[nx][ny] = index
summary += graph[nx][ny]
count += 1
united.append((nx, ny))
# 연합 국가끼리 인구를 분배
for i, j in united:
graph[i][j] = summary // count
total_count = 0
# 더 이상 인구 이동을 할 수 없을 때까지 반복
while True:
union = [[-1] * n for _ in range(n)]
index = 0
for i in range(n):
for j in range(n):
if union[i][j] == -1: # 해당 나라가 아직 처리되지 않았다면
process(i, j, index)
index += 1
# 모든 인구 이동이 끝난 경우
if index == n * n:
break
total_count += 1
# 인구 이동 횟수 출력
print(total_count)
from _collections import deque
def move_population(union_list):
for union in union_list:
total = 0
for country in union:
x, y = country
total += world[x][y]
population = total // len(union)
for country in union:
x, y = country
world[x][y] = population
def find_union(x, y):
q = deque()
q.append((x, y))
union = []
union.append((x, y))
while q:
cx, cy = q.popleft()
for k in range(4):
nx = cx + dx[k]
ny = cy + dy[k]
if 0 <= nx < N and 0 <= ny < N and (nx, ny) not in visited:
if L <= abs(world[cx][cy] - world[nx][ny]) <= R:
union.append((nx, ny))
visited.add((nx, ny))
q.append((nx, ny))
if len(union) > 1:
union_list.append(union)
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
if __name__ == '__main__':
N, L, R = map(int, input().split())
world = [list(map(int, input().split())) for _ in range(N)]
answer = 0
while True:
union_list = []
visited = set()
for i in range(N):
for j in range(N):
if (i, j) not in visited:
visited.add((i, j))
find_union(i, j)
if union_list:
move_population(union_list)
answer += 1
else:
break
print(answer)
DFS
import sys
sys.setrecursionlimit(100000)
n, L, R = map(int, input().split())
maps = [list(map(int, input().split())) for _ in range(n)]
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
count = 0
def go(x, y):
for i in range(4):
new_x = x + dx[i]
new_y = y + dy[i]
if 0 <= new_x < n and 0 <= new_y < n and check[new_x][new_y]:
temp = abs(maps[x][y] - maps[new_x][new_y])
if L <= temp <= R:
check[new_x][new_y] = False
stack.append([new_x, new_y])
go(new_x, new_y)
while True:
check = [[True] * n for _ in range(n)]
flag = True
for i in range(n):
for j in range(n):
stack = []
if check[i][j]:
stack.append([i, j])
check[i][j] = False
go(i, j)
if len(stack) > 1:
flag = False
avg = sum([maps[x][y] for x, y in stack]) // len(stack)
for x, y in stack:
maps[x][y] = avg
if flag:
break
count += 1
print(count)
2. C++
#include <bits/stdc++.h>
using namespace std;
// 땅의 크기(N), L, R 값을 입력받기
int n, l, r;
// 전체 나라의 정보(N x N)를 입력받기
int graph[50][50];
int unions[50][50];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, -1, 0, 1};
// 특정 위치에서 출발하여 모든 연합을 체크한 뒤에 데이터 갱신
void process(int x, int y, int index) {
// (x, y)의 위치와 연결된 나라(연합) 정보를 담는 리스트
vector<pair<int, int> > united;
united.push_back({x, y});
// 너비 우선 탐색 (BFS)을 위한 큐 라이브러리 사용
queue<pair<int, int> > q;
q.push({x, y});
unions[x][y] = index; // 현재 연합의 번호 할당
int summary = graph[x][y]; // 현재 연합의 전체 인구 수
int count = 1; // 현재 연합의 국가 수
// 큐가 빌 때까지 반복(BFS)
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
// 현재 위치에서 4가지 방향을 확인하며
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
// 바로 옆에 있는 나라를 확인하여
if (0 <= nx && nx < n && 0 <= ny && ny < n && unions[nx][ny] == -1) {
// 옆에 있는 나라와 인구 차이가 L명 이상, R명 이하라면
int gap = abs(graph[nx][ny] - graph[x][y]);
if (l <= gap && gap <= r) {
q.push({nx, ny});
// 연합에 추가하기
unions[nx][ny] = index;
summary += graph[nx][ny];
count += 1;
united.push_back({nx, ny});
}
}
}
}
// 연합 국가끼리 인구를 분배
for (int i = 0; i < united.size(); i++) {
int x = united[i].first;
int y = united[i].second;
graph[x][y] = summary / count;
}
}
int totalCount = 0;
int main(void) {
cin >> n >> l >> r;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> graph[i][j];
}
}
// 더 이상 인구 이동을 할 수 없을 때까지 반복
while (true) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
unions[i][j] = -1;
}
}
int index = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (unions[i][j] == -1) { // 해당 나라가 아직 처리되지 않았다면
process(i, j, index);
index += 1;
}
}
}
// 모든 인구 이동이 끝난 경우
if (index == n * n) break;
totalCount += 1;
}
// 인구 이동 횟수 출력
cout << totalCount << '\n';
}
Author And Source
이 문제에 관하여(176. 인구 이동), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@corone_hi/176.-인구-이동저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
좋은 웹페이지 즐겨찾기
