반응형
알고리즘 분류 : DFS
인접한 국가 간의 연합을 통해 인구 이동을 하는 문제다. 연합은 인접한 두 국가 간의 인구 차이가 L 이상, R 이하일 때만 가능하다. 인구 차이가 이 범위를 벗어난다면 연합을 할 수 없고, 인구 이동을 할 수 없다. 이 문제는 그래프에서 연결 요소 개수를 찾는 문제와 비슷하다.
- DFS를 통해 연합 가능한 국가가 몇 개인지 찾는다. (1, 1)부터 (N, N)까지 전체 국가를 탐색하면서 방문하지 않은 국가라면 DFS를 호출한다.
- DFS 탐색을 진행하면서 연합 가능한 국가가 있다면, 연합 국가 개수를 카운트하고, 인구 수의 합을 저장한다.
- 또한 DFS 탐색을 하면서 별도로 연합 국가의 경로를 기록해둔다. 아래 소스코드에서는 moving 이라는 이름의 배열을 사용했다.
- 한 번의 DFS 탐색이 끝나면, 카운트가 1이 넘는지 확인한다. 카운트가 1이 넘는다면 연합 가능한 국가가 있는 것이므로, 인구를 이동시킨다.
- 위 과정을 반복하면서, 인구 이동에 변화가 없다면 종료한다.
C++ 소스코드
#include <cstdio> #include <cstring> #define abs(x) (((x)>0)?(x):(-(x))) using namespace std; struct nation { int x, y; }; int N, L, R, cnt, ans; int a[50][50]; bool check[50][50], moving[50][50]; const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1}; int dfs(int x, int y) { check[x][y] = true; int population = a[x][y]; for (int k=0; k<4; k++) { int nx = x+dx[k], ny = y+dy[k]; if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue; int diff = abs(a[x][y]-a[nx][ny]); if (diff < L || diff > R || check[nx][ny]) continue; moving[nx][ny] = true; cnt++; population += dfs(nx, ny); } return population; } void migrate(int p) { for (int i=0; i<N; i++) { for (int j=0; j<N; j++) { if (moving[i][j]) { a[i][j] = p; moving[i][j] = false; } } } } void solve() { int ans = 0; while (true) { bool moved = false; memset(check, false, sizeof(check)); for (int i=0; i<N; i++) { for (int j=0; j<N; j++) { if (!check[i][j]) { cnt = 1; int population = dfs(i, j)/cnt; if (cnt > 1) { a[i][j] = population; migrate(population); moved = true; } } } } if (moved) ans++; else break; } printf("%d\n", ans); } int main() { scanf("%d %d %d", &N, &L, &R); for (int i=0; i<N; i++) { for (int j=0; j<N; j++) { scanf("%d", &a[i][j]); } } solve(); return 0; }
PyPy3 소스코드
import sys input = sys.stdin.readline sys.setrecursionlimit(10000) N, L, R = map(int, input().split()) a = [list(map(int, input().split())) for _ in range(N)] check = [[False]*N for _ in range(N)] moving = [[False]*N for _ in range(N)] cnt = 0 def dfs(x, y): global cnt check[x][y] = True population = a[x][y] for dx, dy in (-1, 0), (0, 1), (1, 0), (0, -1): nx, ny = x+dx, y+dy if nx < 0 or nx >= N or ny < 0 or ny >= N: continue if not check[nx][ny] and L <= abs(a[nx][ny]-a[x][y]) <= R: moving[nx][ny] = True cnt += 1 population += dfs(nx, ny) return population def migrate(p): for i in range(N): for j in range(N): if moving[i][j]: a[i][j] = p moving[i][j] = False def solve(): global check, cnt ans = 0 while True: moved = False check = [[False]*N for _ in range(N)] for i in range(N): for j in range(N): if not check[i][j]: cnt = 1 population = dfs(i, j)//cnt if cnt > 1: a[i][j] = population migrate(population) moved = True if moved: ans += 1 else: break print(ans) solve()
✓ Python 3로는 시간 초과가 나오기 때문에, PyPy3로 제출했다.
✓ 속도 개선을 하려면, 유니온 파인드 (Union Find) 알고리즘을 사용해야 할 것으로 보인다.
참고
반응형