오늘 풀어본 문제는 인구 이동 이라는 문제이다.
1. 문제 요약
- N*N 크기는 1*1 칸으로 이루어진 나라들이다. 각 나라들에는 인구가 있다.
- 인접한 나라의 인구수 차이가 L명 이상 R명 이하라면, 하루 동안 연합이 된다
- 연합의 인구수 / 연합을 이루는 나라 개수 만큼 인구를 나눠 갖는다.
- 소수점 계산 X
- 인구 이동이 며칠간 발생하는가?
2. 입출력
- (1 ≤ N ≤ 50)
- (1 ≤ L, R ≤ 100)
- 인구이동최대 횟수 : 2000
3. 알고리즘
-
하루 동안 전체 칸을 방문하며 BFS/DFS를 수행
-
BFS/DFS는 모든 칸을 최대 한 번만 방문
-
따라서 하루 시간복잡도 = O(N²)
-
인구 이동은 최대 2000일 동안 반복될 수 있으므로
전체 시간복잡도 = O(2000 × N²) ≈ O(N²)
- N = 50일 때
최대 연산량은 약 5,000,000 연산
구현 문제이다.
해당 문제의 중요한 점은, N * N을 한 번 다 돌면서, 몇 개의 연합이 생겼는지를 모두 구해낸 후 인구수를 바꿔주어야 한다.
그리고 인구가 변하지 않을 때 까지 위 과정을 반복해야 한다.
그래서 난 3중 for문을 사용했다.
while (true) {
boolean visit[][] = new boolean[N][N];
boolean flag = true;
//N*N 반복문 전, 새롭게 바뀐 인구수를 저장할 [N][N] 배열을 만든다.
//기존 배열을 깊은 복사해준 게 포인트다.
for(int i=0; i<N; i++) {
NEXT_WORLD[i] = Arrays.copyOf(WORLD[i], N);
}
for(int i = 0; i<N; i++)
{
for(int j=0; j<N; j++) {
Info start = new Info(i, j);
if(visit[i][j])
continue;
visit[i][j] = true;
Queue<Info> queue = new ArrayDeque<>();
queue.add(start);
//현재 i, j에서 시작했을 때 연합국을 탐색한다.
//반환값은 모든 연합국의 총 인구수이다.
int unionPeopleCnt = findUnion(start, WORLD[i][j], visit, queue);
//만약 총 인구 수가 현재 나라 인구수와 같다면? 연합국이 없다는 의미이다.
if(unionPeopleCnt == WORLD[i][j])
continue;
//NEXT_WORLD 배열에 해당 연합국들의 새로운 인구수를 저장한다.
//현재 나라의 인구 수와, 이후 업데이트 될 인구수 두 데이터는 분리되어야 한다.
calculatePeople(queue, unionPeopleCnt);
//flag가 false라면, 최소 한 번은 인원 변동이 이루어졌다는 뜻이다.
flag = false;
}
}
//전체 맵을 다 본 후, 인원 재배치가 이루어짐
if(flag)
break;
answer++;
WORLD = NEXT_WORLD;
}위 로직이 메인 로직이다! 다른 코드 함수들은 함수 분리화 용도에 가깝다.
전체 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Queue;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.StringTokenizer;
class Info {
int r;
int c;
public Info(int r, int c)
{
this.r = r;
this.c = c;
}
}
public class Main {
static int [][] WORLD;
static int [][] NEXT_WORLD;
static int N, L, R;
static int dirR[] = {1,-1,0,0};
static int dirC[] = {0,0,1,-1};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
L = Integer.parseInt(st.nextToken());
R = Integer.parseInt(st.nextToken());
WORLD = new int[N][N];
NEXT_WORLD = new int[N][N];
for(int i = 0; i<N; i++)
{
st = new StringTokenizer(br.readLine());
for(int j=0; j<N; j++){
WORLD[i][j] = Integer.parseInt(st.nextToken());
}
}
int answer = 0;
while (true) {
boolean visit[][] = new boolean[N][N];
boolean flag = true;
for(int i=0; i<N; i++) {
NEXT_WORLD[i] = Arrays.copyOf(WORLD[i], N);
}
for(int i = 0; i<N; i++)
{
for(int j=0; j<N; j++) {
Info start = new Info(i, j);
if(visit[i][j])
continue;
visit[i][j] = true;
Queue<Info> queue = new ArrayDeque<>();
queue.add(start);
int unionPeopleCnt = findUnion(start, WORLD[i][j], visit, queue);
if(unionPeopleCnt == WORLD[i][j])
continue;
flag = false;
calculatePeople(queue, unionPeopleCnt);
}
}
//전체 맵을 다 본 후, 인원 재배치가 이루어짐
if(flag)
break;
answer++;
WORLD = NEXT_WORLD;
}
System.out.println(answer);
}
static void print() {
for(int i=0; i<N; i++){
for(int j=0; j<N; j++){
System.out.print(NEXT_WORLD[i][j]+" ");
}
System.out.println();
}
}
static int findUnion(Info now, int people, boolean[][] visit, Queue<Info> queue) {
int total = 0;
visit[now.r][now.c] = true;
for(int i = 0; i < 4; i++){
int nr = now.r + dirR[i];
int nc = now.c + dirC[i];
if(!checkArragne(nr, nc) || visit[nr][nc])
continue;
Info next = new Info(nr, nc);
if(!isUnion(now, next))
continue;
queue.add(next);
visit[nr][nc] = true;
total += findUnion(next, WORLD[nr][nc], visit, queue);
}
return total + people;
}
static boolean isUnion(Info now, Info next)
{
int gap = Math.abs(WORLD[now.r][now.c] - WORLD[next.r][next.c]);
return L <= gap && gap <= R;
}
static boolean checkArragne(int r, int c)
{
if(r < 0 || c < 0 || r >= N || c >= N)
return false;
return true;
}
static void calculatePeople(Queue<Info> queue, int unionPeopleCnt)
{
int newPeopleCnt = unionPeopleCnt / queue.size();
for(Info info : queue)
NEXT_WORLD[info.r][info.c] = newPeopleCnt;
}
}
레~전드 용량 차지에 레~전드 느리다.
ㅠㅠㅠ
4. BFS 버전
나의 코드에서 더 깔끔해질 수 있는 방법은 다음과 같다.
- NEW_WORLD 이차원 배열이 필요없다.
- 그냥 BFS/DFS로 하나의 연합 파악 후, 동일한 배열에서 갱신해주어도 된다.
- 어차피 visit 배열이 다른 연합에 속한 인자로의 접근을 막는다.
- DFS의 recursion overhead 대신, BFS를 사용하자.
- 해당 문제는 꼭 DFS를 쓰지 않아도 되었다. 그렇다면 BFS를 지양하자.
그 다음 인구수를 저장할 새로운 배열을 굳이 사용하지 않아도 됐는데, 간과했던 점이다.
아래는 BFS로 푼 버전이다.
import java.io.*;
import java.util.*;
class Main {
static int N, L, R;
static int[][] WORLD;
static int[] dr = {1, -1, 0, 0};
static int[] dc = {0, 0, 1, -1};
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
L = Integer.parseInt(st.nextToken());
R = Integer.parseInt(st.nextToken());
WORLD = new int[N][N];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
WORLD[i][j] = Integer.parseInt(st.nextToken());
}
}
int days = 0;
while (true) {
boolean[][] visited = new boolean[N][N];
boolean moved = false;
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
if (visited[r][c]) continue;
// BFS 시작
List<int[]> union = new ArrayList<>();
Queue<int[]> q = new ArrayDeque<>();
q.add(new int[]{r, c});
visited[r][c] = true;
union.add(new int[]{r, c});
int sum = WORLD[r][c];
while (!q.isEmpty()) {
int[] cur = q.poll();
int cr = cur[0], cc = cur[1];
for (int d = 0; d < 4; d++) {
int nr = cr + dr[d];
int nc = cc + dc[d];
if (!inRange(nr, nc) || visited[nr][nc]) continue;
int diff = Math.abs(WORLD[cr][cc] - WORLD[nr][nc]);
if (diff < L || diff > R) continue;
visited[nr][nc] = true;
q.add(new int[]{nr, nc});
union.add(new int[]{nr, nc});
sum += WORLD[nr][nc];
}
}
// 연합이 2개 이상일 때 갱신 발생
if (union.size() > 1) {
moved = true;
int newVal = sum / union.size();
for (int[] pos : union) {
WORLD[pos[0]][pos[1]] = newVal;
}
}
}
}
if (!moved) break;
days++;
}
System.out.println(days);
}
static boolean inRange(int r, int c) {
return r >= 0 && r < N && c >= 0 && c < N;
}
}
5. 최적화 버전
해당 문제에서 가장 빠른 시간을 가진 사람의 코드를 들여다보니, 다음과 같은 특징이 있었다.
나 : 모든 N*N에서 bfs 호출
빠른 사람 : 오른쪽 or 아래쪽 나라와 연합 조건이 성립될 때만 BFS 시작
참고용으로 링크를 올린다.
