접근
연합을 알기 위해서는 결국 bfs를 통해 조건을 만족하며 인접한 국가들을 모두 찾아야 한다. 대략적인 풀이 순서는 다음과 같다.
1. 아직 연합에 소속되지 않은 국가를 찾는다
2. 인접한 국가에 대해서 국경을 열 수 있는지 조건을 확인한다
3. bfs로 서로 인접한 모든 국가들을 연합에 소속시킨다
4. 해당 연합의 인구 이동을 반영한다
5. 위 과정을 더 이상 인구 이동이 없을 때까지 반복한다
1) 먼저 이차원 visited 배열을 통해 해당 국가가 이미 연합에 속해있는지를 확인하여 불필요하게 반복적인 연산을 피할 필요가 있다. 이때 boolean으로 설정해도 되지만, 나는 이후에 인구 이동을 편하게 계산하기 위해 int로 설정하여 연합의 번호를 저장하도록 했다. 따라서 어떤 연합에도 속하지 않을 경우 0값을 가지게 된다. 이 visited 배열은 새로운 날마다 초기화된다.
2, 3) 연합에 속하지 않은 국가를 찾았다면, bfs로 인구수를 비교하며 동일한 연합의 국가들을 찾는다. 인접은 상하좌우 4방향을 찾아야 한다. 만약 인접 인덱스가 전체 배열의 범위를 벗어나거나, 이미 어떤 연합에 속해있을 경우에는 넘어간다. 연합 국가를 찾을 때마다 그 인구수와 개수를 누적한다. 그렇게 연합 번호, 누적 인구수, 전체 국가수를 가진 Union이라는 객체를 만든다.
4) 위에서 구한 Union 객체를 통해 인구를 이동시킨다. visited 배열에 저장된 값과 연합 번호가 같은 국가들에 한해서 인구 값을 갱신한다.
5) 만약 Union 객체의 국가 수가 1이라면 연합이 이루어지지 않아 인구 이동이 발생하지 않았다는 것을 의미한다. 따라서 알고리즘 계산을 종료한다.
사실 처음에는 위에서 말한 boolean 방법으로 연합 소속 여부만 확인하고, 별도로 큐에 저장해 그에 속하는 국가들에만 접근하여 인구를 갱신하는 코드를 짰었다. 하지만 실행 시간에 차이가 나지 않았기 때문에 위 방법이 가독성 측면에서는 더 좋다고 생각하여 이렇게 포스팅을 하게 되었다.
코드
package week9;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class BJ16234 {
static class Pos{
int x, y;
public Pos(int x, int y) {
this.x = x;
this.y = y;
}
}
static class Union{
int unionNum, populationSum, countryCnt;
public Union(int unionNum, int populationSum, int countryCnt) {
this.unionNum = unionNum;
this.populationSum = populationSum;
this.countryCnt = countryCnt;
}
}
static int[][] countryMap, visited;
static int n, l, r;
static int[] dx = {-1, 0, 1, 0};
static int[] dy = {0, 1, 0, -1};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
// 입력값 저장
st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
l = Integer.parseInt(st.nextToken());
r = Integer.parseInt(st.nextToken());
countryMap = new int[n][n];
visited = new int[n][n];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++)
countryMap[i][j] = Integer.parseInt(st.nextToken());
}
// 인구 이동
int dayCnt = 0;
while (checkBorder()) {
visited = new int[n][n];
dayCnt++;
}
System.out.println(dayCnt);
}
private static boolean checkBorder() {
// 변수 초기화
boolean isUnion = false;
int unionNum = 1;
// 인근 나라 인구 확인
for (int x = 0; x < n; x++) {
for (int y = 0; y < n; y++) {
if(visited[x][y] != 0) continue;
// 연합끼리 국경 열기
Union union = openBorder(x, y, unionNum++);
// 두 개 이상의 국가가 연합이 되었다면 인구이동
if(union.countryCnt > 1){
isUnion = true;
movePopulation(union);
}
}
}
return isUnion;
}
private static void movePopulation(Union union) {
int newPopulation = union.populationSum / union.countryCnt;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if(visited[i][j] != union.unionNum) continue;
countryMap[i][j] = newPopulation;
}
}
}
private static Union openBorder(int x, int y, int unionNum) {
// 변수 초기화
Queue<Pos> q = new LinkedList<>();
int populationSum = 0;
int countryCnt = 0;
// 인접한 국가를 bfs로 탐색
q.add(new Pos(x, y));
while(!q.isEmpty()) {
Pos cur = q.poll();
if(visited[cur.x][cur.y] != 0) continue;
visited[cur.x][cur.y] = unionNum;
populationSum += countryMap[cur.x][cur.y];
countryCnt++;
for (int d = 0; d < 4; d++) {
int nx = cur.x + dx[d];
int ny = cur.y + dy[d];
if (!inBound(nx, ny) || visited[nx][ny] != 0) continue;
int populationSub = Math.abs(countryMap[cur.x][cur.y] - countryMap[nx][ny]);
if (populationSub >= l && populationSub <= r)
q.add(new Pos(nx, ny));
}
}
return new Union(unionNum, populationSum, countryCnt);
}
private static boolean inBound(int x, int y) {
return !(x < 0 || y < 0 || x >= n || y >= n);
}
}