문제 정리
N x N 배열에서 각 칸을 한 나라가 차지한다고 할때
인접한 두 나라의 인구 차이가 L 이상 R 이하일 때 연합이 가능하다
하나의 연합이 된 나라는 하루밤 동안 서로 인구 이동이 가능하다.
인구 이동이 끝난 후 인구수는
(연합된 나라의 인구 수) / (연합국 수) 이다.
하루밤이 지나면 연합을 해체한다.
이 과정을 모든 나라가 연합이 불가능 할 때까지 반복하고
연합이 며칠 동안 가능한지 구하는게 목표다.
입력
N L R //N=배열 크기, 인구 차이가 L 이상 R 이하
배열 정보
출력
인구 이동이 며칠동안 발생하는지
idea 정리
이 문제를 딱 읽고 정리했을 때 가장 헷갈렸던 부분이
인구 차이가 L 이상 R 이하일 때 연합이 생긴다 였다.
- 연합된 모든 나라의 인구 차이가 L 이상 R 이하인지,
- 그냥 인접한 나라끼리만 L 이상 R 이하인지.
가 헷갈렸다.
1번이 맞다면 연합국을 계산하는 과정이 매우 복잡해진다.
한 나라를 추가로 연합 할 때마다 기존의 연합국 중에
연합을 해제해야 할 나라가 생기는지 확인하는 작업이 필요하기 때문이다.
처음에는 헷갈렸었는데 다시 생각해보면 1번이 맞는 방식이라면 조건이 더 주어져야한다.
먼저 연합한 나라와 후에 추가할 나라가 동등한 입장이기 때문에(우선순위가 없기 때문에)
먼저 연합한 나라를 뺀다거나 추가하려고 한 나라를 추가하지 않는다는 결정을 할 수가 없다.
그리고 예제 입력 5번을 분석해 보니 2번이 맞는 방식이긴 했다.
bfs를 구현할 때
조심해야할 부분이 있는데
- 땅에서 연합국이 여러개 생길 수 있다
- 한 나라는 하루밤동안 한번의 연합만 가능하다
이렇게 두가지 이다.
2번은 bfs로 구현을 하게 되면 이미 연합을 하고 인구 이동이 끝난 나라가
같은 밤에 다른 연합에도 포함될 수도 있기 때문에 조심해야한다.
질문글 찾아보니 bfs에서 dfs로 바꿨을때 시간이 덜 걸렸다는 글을 발견해서
나도 dfs로 바꿔서 채점 해봤는데 나는 오히려 시간이 더 늘어났다
다른 사람들은 어떻게 구현했나 싶어서 빠른 코드로 몇개 봤는데 union-find를 쓴 사람이 많았다.
dfs도 하나 발견했는데 list를 안쓰고 구현해서 시간이 별로 안걸린거 같다
알고리즘 구성
- 배열을 돌면서 연합국을 형성할 수 있는 지점을 찾는다
- list를 초기화 해준다
- 1번에서 찾은 지점을 기준으로 연합 가능한 나라를 모두 q와 list에 넣어준다
-> 연합 가능한 지점
연합국에 포함된 나라는 모두 방문처리를 해준다
그래야 다른 연합국에 포함되지 않는다 - list에 포함된 모든 연합국의 인구수를 업데이트 해준다
- 배열을 다 돌면 day+1 해준다
- 1번이 불가능 할 때까지 반복한다
구현
//인구 이동
public class Main {
static class Country{
int r,c;
public Country() {
super();
}
public Country(int r, int c) {
super();
this.r = r;
this.c = c;
}
}
static int N, L, R;
static int[][] map;
static boolean[][] visited;
static int[] dr = {-1, 1, 0, 0};
static int[] dc = {0, 0, -1, 1};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
L = Integer.parseInt(st.nextToken());
R = Integer.parseInt(st.nextToken());
map = new int[N][N];
for(int i=0; i<N; i++) {
st = new StringTokenizer(br.readLine(), " ");
for(int j=0; j<N; j++) {
int value = Integer.parseInt(st.nextToken());
map[i][j] = value;
}
}
int cnt = 0;
boolean flag = false;
while(true) {
visited = new boolean[N][N];
flag = false;
for(int i=0; i<N; i++) {
for(int j=0; j<N; j++) {
if(visited[i][j]) continue;
for(int d=0; d<4; d++) {
int nr = i + dr[d];
int nc = j + dc[d];
if(0<=nr && nr<N && 0<=nc && nc<N && !visited[nr][nc]) {
int diff = Math.abs(map[i][j] - map[nr][nc]);
if(L<=diff && diff<=R) {
flag = true;
//연합국이 될 수 있는 지점을 시작으로 bfs
bfs(i, j);
break;
}
}
}
}
}
if(!flag) break; //연합국이 없음
cnt++;
}//end of while
bw.write(cnt + "");
bw.flush();
bw.close();
br.close();
}
static void bfs(int r, int c) {
Queue<Country> q = new LinkedList<>();
List<Country> list = new ArrayList<>();
Country country = new Country(r, c);
q.add(country);
list.add(country);
visited[r][c] = true;
int sum = map[r][c];
while(!q.isEmpty()) {
Country now = q.poll();
for(int d=0; d<4; d++) {
int nr = now.r + dr[d];
int nc = now.c + dc[d];
if(0<=nr && nr<N && 0<=nc && nc<N && !visited[nr][nc]) {
int diff = Math.abs(map[now.r][now.c] - map[nr][nc]);
if(L<=diff && diff<=R) {
Country newC = new Country(nr, nc);
q.add(newC);
list.add(newC);
visited[nr][nc] = true;
sum += map[nr][nc];
}
}
}
}
int size = list.size();
int newPeopleCnt = sum/size;
for(int i=0; i<size; i++) { //인구 update
int countryR = list.get(i).r;
int countryC = list.get(i).c;
map[countryR][countryC] = newPeopleCnt;
}
}
}혹시나 dfs 코드가 궁금하다면
백준 16234 인구 이동 - dfs
결과
위 결과는 bfs 코드이고
dfs 코드의 결과는 444ms가 나왔다
