#16234 인구 이동
난이도 : 골드 5
유형 : 그래프 탐색
16234번: 인구 이동
N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모
www.acmicpc.net
▸ 문제
N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다.
오늘부터 인구 이동이 시작되는 날이다.
인구 이동은 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다.
- 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루동안 연다.
- 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다.
- 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다.
- 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버린다.
- 연합을 해체하고, 모든 국경선을 닫는다.
각 나라의 인구수가 주어졌을 때, 인구 이동이 몇 번 발생하는지 구하는 프로그램을 작성하시오.
▸ 입력
첫째 줄에 N, L, R이 주어진다. (1 ≤ N ≤ 50, 1 ≤ L ≤ R ≤ 100)
둘째 줄부터 N개의 줄에 각 나라의 인구수가 주어진다. r행 c열에 주어지는 정수는 A[r][c]의 값이다. (0 ≤ A[r][c] ≤ 100)
인구 이동이 발생하는 횟수가 2,000번 보다 작거나 같은 입력만 주어진다.
▸ 출력
인구 이동이 몇 번 발생하는지 첫째 줄에 출력한다.
문제 풀이
골드 5 문제치고는 설계부분이 심심치 않아서 당황스러웠다. 전체적인 개념이 어렵지않지만 꼼꼼한 설계가 바탕이 되어야 했다.
원래 골드5가 이정도였나..?
실전이라 생각하고 당황하지않고 침착하게 차근차근 정리해보자!
일단 그래프 탐색문제이다. 어떤 그래프 알고리즘을 쓸지는 문제 조건을 정리하면서 생각해 볼 것이다.
풀이 과정
조건을 정리하여 풀이를 해보면 다음과 같다.
1) 국경선 열리는 조건은 인접한 두 나라의 인구 차이가 'L이상 R이하' 이어야한다.
☛ a국가 : num1 , b국가 : num2 일 때 L <= | num1-num2 | <= R 이어야 국경이 열린다.
2) 한 싸이클에 해당하는 국경을 모두 열고나서 인구 이동을 시작한다. (메소드 실행과정 분리, 순차대로 깔끔하게)
☛ BFS탐색으로 그래프 NxN을 전체 탐색하여 1) 조건을 만족하면 해당 맵의 국경을 모두 연다.
-> 그 다음 연합단위로 인구이동을 시작한다.
☛ 여기서 만약 연합이 없으면 이동이 더이상 안일어나므로 반복 종료!
---- 각 연합마다 반복 구간 --------
3) 연합은 국경이 열려있어 연결되어 있는 한 묶음이다.
☛ DFS탐색으로 하나의 연합을 탐색하여 국가의 갯수와 총 인원을 구한다
4) (연합 총 인원/ 국가 갯수)로 해당 연합에 속해있는 나라 인구 이동을 시작한다.
---- 각 연합마다 반복 종료 --------
5) 모든 탐색이 완료했으면 인구이동 발생횟수를 count해주고 1)으로 다시 돌아간다.
처음 풀이한 코드는 총 3개의 메소드로 나눴다.
- openDoor()메소드 : 현재의 map을 기준으로 조건에 충족했을 시 국경을 열어주는 로직 - BFS
- unionSearch() 메소드 : openDoor()에서 생성된 연합을 찾아 인구 수와 연합 수를 체킹하는 로직 -DFS
- solve() 메소드 : 한 번의 이동을 기준으로 while 반복문을 실행하는 로직
openDoor() 메소드 - BFS 사용
static void openDoor(int x, int y) {
int a_name = n*x +y;
int a_num = map[x][y];
for(int i=0; i<4; i++) {
int nx = x+dx[i];
int ny = y+dy[i];
if(nx<0 || ny<0 || nx>n-1 || ny>n-1) continue;
int b_name= n*nx +ny;
int b_num = map[nx][ny];
int dif = Math.abs(a_num-b_num);
if(union[a_name].contains(b_name) || union[b_name].contains(a_name)) continue;
// a_name, b_name 국경 개방
if(l <= dif && dif <=r) {
flag = true;
// System.out.println(a_name +" ," + b_name+ " 국경 오픈 ");
union[a_name].add(b_name);
union[b_name].add(a_name);
}
}
}
unionSearch() 메소드 - DFS 사용
static void unionSearch(int start) {
int x = start/n;
int y = start%n;
cnt+=1;
sum += map[x][y];
check[start]= true;
for(int i=0; i<union[start].size(); i++) {
int next = union[start].get(i);
int nx = next/n;
int ny = next%n;
if(nx <0 || ny<0 || nx>n-1 || ny>n-1) continue;
if(!check[next]) {
unionSearch(next);
}
}
}
solve() 메소드
static void solve() {
// 열 수 있는 국경이 존재할 때 까지 반복
int move_num =0;
while(true) {
flag = false;
// 1. 국경선 열기
union = new ArrayList[n*n];
for(int i=0; i<n*n; i++) {
union[i] = new ArrayList<>();
}
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
// i,j 나라 탐색
openDoor(i,j);
}
}
// 연합 존재하지 않으면 이동 종료
if(!flag) break;
// 2. 존재하는 연합 탐색 및 인구 이동
move_num ++; // 이동 count+1
check = new boolean[n*n];
List<Integer> visit = new ArrayList<>();
for(int a=0; a<n*n; a++) {
if(union[a].size() >0 && !check[a]) {
cnt =0; sum =0;
// 연합 탐색 시작
unionSearch(a);
//인구 이동 수 계산
int re_population = sum/cnt;
for(int nara=0; nara<n*n; nara++) {
if(check[nara] && !visit.contains(nara)) {
visit.add(nara); // 이미 방문 싸이클 체크
int x = nara/n;
int y = nara%n;
map[x][y] = re_population;
}
}
}
}
}
// 결과 출력
System.out.println("총 이동횟수 : " + move_num);
}
1차 풀이코드
사실 이게 좋은 코드는 아니다. 주먹구구식으로 빠르게 코딩을 하다보니 효율성 측면은 크게 고려하지 않았다. 그래도 전체적인 풀이과정은 알았으니 이제 다시 효율성을 고려하여 코딩해보자.
// #16234 bfs/dfs 인구이동
import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
static int n,l,r;
static int[][] map;
static boolean[] check;
static List<Integer>[] union;
static int cnt, sum;
static boolean flag;
static int[] dx = {-1,1,0,0};
static int[] dy = {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());
map = new int[n][n];
for(int i=0; i<n; i++) {
st = new StringTokenizer(br.readLine());
for(int j=0; j<n; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
solve();
}
static void solve() {
// 열 수있는 국경이 존재할 때 까지 반복
int move_num =0;
while(true) {
flag = false;
// 1. 국경선 열기
union = new ArrayList[n*n];
for(int i=0; i<n*n; i++) {
union[i] = new ArrayList<>();
}
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
// i,j 나라 탐색
openDoor(i,j);
}
}
// 연합 존재하지 않으면 이동 종료
if(!flag) break;
// 2. 존재하는 연합 탐색 및 인구 이동
move_num ++;
check = new boolean[n*n];
List<Integer> visit = new ArrayList<>();
for(int a=0; a<n*n; a++) {
if(union[a].size() >0 && !check[a]) {
cnt =0; sum =0;
// 연합 탐색 시작
unionSearch(a);
//인구 이동 수 계산
int re_population = sum/cnt;
for(int nara=0; nara<n*n; nara++) {
if(check[nara] && !visit.contains(nara)) {
visit.add(nara); // 이미 방문 싸이클 체크
int x = nara/n;
int y = nara%n;
map[x][y] = re_population;
}
}
}
}
}
// 결과 출력
System.out.println("총 이동횟수 : " + move_num);
}
static void unionSearch(int start) {
int x = start/n;
int y = start%n;
cnt+=1;
sum += map[x][y];
check[start]= true;
for(int i=0; i<union[start].size(); i++) {
int next = union[start].get(i);
int nx = next/n;
int ny = next%n;
if(nx <0 || ny<0 || nx>n-1 || ny>n-1) continue;
if(!check[next]) {
unionSearch(next);
}
}
}
static void openDoor(int x, int y) {
int a_name = n*x +y;
int a_num = map[x][y];
for(int i=0; i<4; i++) {
int nx = x+dx[i];
int ny = y+dy[i];
if(nx<0 || ny<0 || nx>n-1 || ny>n-1) continue;
int b_name= n*nx +ny;
int b_num = map[nx][ny];
int dif = Math.abs(a_num-b_num);
if(union[a_name].contains(b_name) || union[b_name].contains(a_name)) continue;
// a_name, b_name 국경 개방
if(l <= dif && dif <=r) {
flag = true;
union[a_name].add(b_name);
union[b_name].add(a_name);
}
}
}
}
최종 풀이코드
효율성측면을 고려하여 코드를 다시 짜봤다.
다시 생각해보면 모든 연합을 다 찾은 다음에 한 번에 무빙을 할 필요가 없었다. 한 싸이클 안에서 각 연합은 독립적으로 움직이기 때문에 각 연합을 찾을 때마다 이동을 해주고 다시 메모리를 리셋해주면 공간 효율이 크게 증가할 수 있다.
그래서 변화된 부분은 국경을 열고 인구 이동하는 부분을 한 싸이클 안에 한 번에 실행시켰다. 그러니 메모리 사용도 줄이고 시간도 확실히 줄어들었다.
위의 1차 풀이랑은 solve()메소드를 보면 차이를 쉽게 확인할 수 있다.
import java.io.*;
import java.util.*;
public class Main {
static class Union{
int x;
int y;
public Union(int x, int y) {
this.x = x;
this.y = y;
}
}
static int n,l,r,cnt,sum;
static int[][] map;
static int[] check;
static Queue<Union> q;
static int[] dx = {-1,1,0,0};
static int[] dy = {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());
map = new int[n][n];
check = new int[n*n];
for(int i=0; i<n; i++) {
st = new StringTokenizer(br.readLine());
for(int j=0; j<n; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
solve();
}
static void solve() {
// 열 수있는 국경이 존재할 때 까지 반복
int move_num =0;
boolean flag = true;
while(flag) {
flag = false;
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
cnt =0; sum=0;
// i,j 나라 탐색
if(check[n*i +j] ==0) {
if(condition(i,j)) { //인접나라에 국경 열 곳이 있는지 확인
openDoor(i,j);
// 인구 이동 수 계산
int re_population = sum/cnt;
// 인구 이동
populationMove(i,j, re_population);
flag = true;
}
}
}
}
if(flag) move_num++;
else break;
check = new int[n*n];
}
// 결과 출력
System.out.println("총 이동횟수 : " + move_num);
}
static boolean condition(int i, int j) {
for(int k = 0; k < 4; k++) {
int nx = i + dy[k];
int ny = j + dx[k];
if(nx<0 || ny<0 || nx>n-1 || ny>n-1) continue;
int dif = Math.abs(map[nx][ny] - map[i][j]);
if(l <= dif && dif <=r) {
return true;
}
}
return false;
}
static void populationMove(int x, int y, int moveNum) {
int a_city = n*x +y;
q = new LinkedList<>();
q.add(new Union(x,y));
check[a_city] = -1;
map[x][y] = moveNum;
while(!q.isEmpty()) {
Union pos = q.poll();
int px = pos.x;
int py = pos.y;
for(int i=0; i<4; i++) {
int nx = px+dx[i];
int ny = py+dy[i];
if(nx<0 || ny<0 || nx>n-1 || ny>n-1) continue;
int b_city = n*nx + ny;
if(check[b_city] !=1) continue;
check[b_city] = -1;
map[nx][ny] = moveNum;
q.add(new Union(nx,ny));
}
}
}
static void openDoor(int x, int y) {
int a_city = n*x +y;
q= new LinkedList<>();
q.add(new Union(x,y));
check[a_city] = 1;
sum = map[x][y];
cnt=1;
while(!q.isEmpty()) {
Union pos = q.poll();
int px = pos.x;
int py = pos.y;
int a_pop = map[px][py];
for(int i=0; i<4; i++) {
int nx = px+dx[i];
int ny = py+dy[i];
if(nx<0 || ny<0 || nx>n-1 || ny>n-1) continue;
int b_city = n*nx + ny;
int b_pop = map[nx][ny];
if(check[b_city] !=0) continue;
int dif = Math.abs(a_pop-b_pop);
// a_name, b_name 국경 개방
if(l <= dif && dif <=r) {
check[b_city] =1;
q.add(new Union(nx,ny));
cnt++;
sum += b_pop;
}
}
}
}
}
'Dot Algo∙ DS > PS' 카테고리의 다른 글
| [BOJ] 백준 1261번 알고스팟 (Java) (0) | 2021.05.15 |
|---|---|
| [BOJ] 백준 9663번 N-Queen 백트래킹 (Java) (0) | 2021.05.14 |
| [BOJ] 백준 16916번 부분 문자열 KMP (Java) (0) | 2021.05.11 |
| [BOJ] 백준 1389번 케빈 베이컨의 6단계 법칙 (Java) (0) | 2021.05.09 |
| [프로그래머스] 2021 카카오/ 매출 하락 최소화 (Java) (0) | 2021.05.06 |
