문제
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번 보다 작거나 같은 입력만 주어진다.
출력
인구 이동이 몇 번 발생하는지 첫째 줄에 출력한다.
-----------------------------------------------------------------------------------------------------------------------------------
해결방법
1. 시뮬레이션 : 인구 이동에 대한 기준에 맞춰서 지도를 바꾼다
2. BFS(너비우선탐색) : ArrayList와 boolean[]로 너비우선 탐색을 진행한다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class 인구이동 {
static int N,L,R, A[][],ans;
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());
A = new int[N][N];
for (int i = 0; i < N; i++) {
st= new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
A[i][j] = Integer.parseInt(st.nextToken());
}
}
ans =0;
while(true) {
//바꾸는 h집합
ArrayList<ArrayList> al = new ArrayList<ArrayList>();
// 바꾸는 걸 찾자 이제
// 방문한건 visitied[]로
boolean [] visitied = new boolean[N*N];
for (int n = 0; n < N*N; n++) {
if(visitied[n])continue;
ArrayList<Integer> h = new ArrayList<Integer>();
h.add(n);
visitied[n]= true;
int i = 0;
int sum=A[n/N][n%N];
while(i<h.size()) {
int nn = h.get(i);
int r = nn/N;
int c = nn%N;
if(r>0&& !visitied[nn-N]) {
int d = Math.abs(A[r][c]-A[r-1][c]);
if(d>=L&& d<=R) {
h.add(nn-N);
visitied[nn-N]=true;
sum+=A[r-1][c];
}
}
if(c>0&& !visitied[nn-1]) {
int d = Math.abs(A[r][c]-A[r][c-1]);
if(d>=L&& d<=R) {
h.add(nn-1);
visitied[nn-1]=true;
sum+=A[r][c-1];
}
}
if(r<N-1&& !visitied[nn+N]) {
int d = Math.abs(A[r][c]-A[r+1][c]);
if(d>=L&& d<=R) {
h.add(nn+N);
visitied[nn+N]=true;
sum+=A[r+1][c];
}
}
if(c<N-1&& !visitied[nn+1]) {
int d = Math.abs(A[r][c]-A[r][c+1]);
if(d>=L&& d<=R) {
h.add(nn+1);
visitied[nn+1]=true;
sum+=A[r][c+1];
}
}
i++;
}
if(h.size()>1) {
h.add(sum/h.size());
al.add(h);
}
}
//hs 집합이 비어있으면 break;
if(al.isEmpty())break;
for (ArrayList<Integer> h : al) {
int s = h.size();
for (int j = 0; j < s-1; j++) {
int nn =h.get(j);
int r = nn/N;
int c = nn%N;
A[r][c]= h.get(s-1);
; }
}
// 아니면 ans+=1;
ans++;
}
System.out.println(ans);
}
}
전체 코드 부터 우선 첨부한다.
풀이 방법은 시뮬레이션 위주로 구현하였다. bfs는 부가 사항....
우선 A[][]에 국가의 정보가 저장되어 있는데, 이것을 인접 국가들의 평균으로 바꾸어주어야 한다
인접국가의 평균으로 바뀌는 작업은
인구 이동은 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다.
- 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루동안 연다.
{요구사항 1}
if(r>0&& !visitied[nn-N]) {
int d = Math.abs(A[r][c]-A[r-1][c]);
if(d>=L&& d<=R) {
h.add(nn-N);
visitied[nn-N]=true;
sum+=A[r-1][c];
}
}
if(c>0&& !visitied[nn-1]) {
int d = Math.abs(A[r][c]-A[r][c-1]);
if(d>=L&& d<=R) {
h.add(nn-1);
visitied[nn-1]=true;
sum+=A[r][c-1];
}
}
if(r<N-1&& !visitied[nn+N]) {
int d = Math.abs(A[r][c]-A[r+1][c]);
if(d>=L&& d<=R) {
h.add(nn+N);
visitied[nn+N]=true;
sum+=A[r+1][c];
}
}
if(c<N-1&& !visitied[nn+1]) {
int d = Math.abs(A[r][c]-A[r][c+1]);
if(d>=L&& d<=R) {
h.add(nn+1);
visitied[nn+1]=true;
sum+=A[r][c+1];
}
}40번쨰 줄 : 두 나라가 공유하는 국경선을 오늘 하루동안 연다. 에 맞춰진 코드이다.
- 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다
열릴 수 있는 국경선은 아래와 같이 구현된다.
for (int n = 0; n < N*N; n++) { // n을 r,c로 따로 설정하지 않은 이유는 loop를 빠져나가기 쉽게 하기 위함+ h라는 인접 국가 리스트에 이용하기 편함이다.
if(visitied[n])continue; // 만약 이미 다른 인접국 리스트에 들어가 있다면 제외한다.
ArrayList<Integer> h = new ArrayList<Integer>(); // 인접국 리스트를 저장할 배열
h.add(n); // 시작하는 지점을 넣어준다
visitied[n]= true; // 한번 방문한 곳은 타 bfs에 의하여 다른 곳에서 true값을 가진다.
int i = 0; // i를 통해 bfs를 돈다. ArrayList 를 queue처럼 이용하기 위함이다.
int sum=A[n/N][n%N]; // sum을 따로 loop계산하지 않기 위해 미리 더해준다.
while(i<h.size()) {
int nn = h.get(i);
int r = nn/N;
int c = nn%N;
{요구사항 1}
i++;
} // 이 반복문이 bfs를 구현한 것이다.
if(h.size()>1) {
h.add(sum/h.size()); // 이후 값 추가를 위하여 계산을 한번 더 하지 않기 위하여 미리 h:인접 국가 리스트의 끝에 변경할 인구수를 넣어준다.
al.add(h); // 변경되어야할 집합을 ArrayList에 삽입한다.
}
}여기에서 열릴 수 있는 국경선 집합을 나타내기 위한 것들이 중요하게 이용되었다.
ArrayList안에 ArrayList로 구현하는 방법을 이용하였다. al 은 바뀔 수 있는 곳을 모두 넣는 곳이다.
- 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다.
인접한 칸을 넣은 연합이 h이고 이 h의 리스트가 al에 저장된다.
- 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버린다.
아래를 통해서 각 칸의 인구수를 구해서 h에 넣어준다.
if(h.size()>1) { // 1보다 클 경우 넣어야 국가가 하나인 경우를 제외하고 넣게 된다.
h.add(sum/h.size());
al.add(h);
}- 연합을 해체하고, 모든 국경선을 닫는다.
‡
//hs 집합이 비어있으면 break;
if(al.isEmpty())break; // 만약 변경할 것이 없으면 더이상 인구이동을 멈춘다.
for (ArrayList<Integer> h : al) {
int s = h.size();
for (int j = 0; j < s-1; j++) {
int nn =h.get(j);
int r = nn/N;
int c = nn%N;
A[r][c]= h.get(s-1);
}
}
// 아니면 ans+=1;
ans++;위 코드가 연합을 해체하기 전 과정이다. 해체 직전에 A의 값을 변경해 준다.
그리고 변경이 일어난 이후에는 ans에 1을 더해주고, 다시 처음으로 돌아가 visitied[][]를 모두 false로 만들고
인접국을 다시 탐색하게 된다.
사실 이렇게 풀어서 별로 효율적인 코드는 아닌 것 같다.. 차라리 Queue로 구현해야 했나 라는 생각은 들지만,
이미 ArrayList로 짜기 시작한거 포기하지 않는다! ㅋㅋ
다 구현해 낸게 중요한거라고 생각한다.
ArrayList로 구현해보고 싶은 사람에겐 괜찮은 코드가 되지 않나 싶다!
'코딩테스트 연습 > 백준' 카테고리의 다른 글
| [ 백준 / 13460 ] Gold 2 구슬탈출2 : JAVA (0) | 2020.07.20 |
|---|---|
| [ 백준 / 17406 ] 배열돌리기4 - java (0) | 2020.07.09 |
| [ 백준 17281번 ] Gold IV - ⚾ ( 야구) - 자바 (0) | 2020.07.04 |
| [ 백준 / 19238번 ] Gold IV - 스타트 택시 ( java ) (0) | 2020.06.29 |
| [ 백준 / 14503번 ] Gold V - 로봇 청소기 - 자바 ( java) (0) | 2020.06.23 |
