728x90
인구 이동
해설
이 문제는 2차원 배열의 탐색 문제
이기 때문에 좌표 형태를 그래프로 바꿔야 한다는 생각을 먼저 하였다.
문제의 입력 예시 4번을 가지고 해설할 것이다.
입력
N : 3, L : 5, R : 10
3 5 10
10 15 20
20 30 25
40 22 10
L <= 인구차이(P) <= R
5 <= p <= 10
(x, y)
: 나라 - or |
: 국경선, #
: 인구수
(0, 0 #10) (0, 1 #15) (0, 2 #20)
(1, 0 #20) (1, 1 #30) (1, 2 #25)
(2, 0 #40) (2, 1 #22) (2, 2 #10)
입력 예시를 좌표 형태로 나타내면 위와 같다.
이 상태에서, 인접한 나라들을 탐색하여 국경선을 열 수 있는지 확인
해야 한다. 즉, 인접한 두 나라의 인구차이가 L 명 이상 R 명 이하라면 두 나라가 공유하는 국경선을 하루동안 열 수 있다.
인접한 나라를 탐색하기 위해서는 상,하,좌,우
로 탐색하면 된다.
// 상하좌우 : 인접한 나라를 판단하기 위함
private static int[] dx = {-1, 1, 0, 0};
private static int[] dy = {0, 0, 1, -1};
인접한 나라들을 탐색하기 위해서 BFS
방법을 사용하면 된다.
(0, 0) 에 위치한 나라를 시작으로 인접한 나라를 탐색하면 된다.
첫 번째 BFS 탐색 결과 : 첫 번째 연합
(0, 0 #10)-(0, 1 #15)-(0, 2 #20)
| |
(1, 0 #20)-(1, 1 #30)-(1, 2 #25)
|
(2, 1 #22)
위 그래프 형태가 첫 번째 연합의 결과이다. 따라서 인구 이동
이 1번 일어난다. 인구 이동이 일어난 후에는 연합간의 인구를 균등 분배 해야 하므로 문제에서 주어진 식대로 계산하면 아래와 같다.
- 연합을 이루고 있는 각 칸의 인구수 = 연합의 인구수 / 연합을 이루고 있는 칸의 개수
- 142(10 + 15 + 20 + 20 + 22 + 25 + 30) / 7 = 20
인구 이동
(0, 0 #20)-(0, 1 #20)-(0, 2 #20)
| |
(1, 0 #20)-(1, 1 #20)-(1, 2 #20)
|
(2, 1 #20)
따라서, 연합의 인구수를 계산하기 위한 변수와, 칸의 개수를 나타내는 변수가 필요하다는 것을 알 수 있다. 또한, 연합에 속하는 나라들을 저장하기 위한 자료구조도 필요하다.
BFS 탐색 결과 현재 국경선으로 연결되어 있는 나라들은 방문(Visited)
한 나라들이므로, 다음 BFS 탐색 때 방문 여부를 체크하여 인구 이동이 더 이상 일어나지 않을 때 까지 반복하면 된다.
모든 국경선 닫고, 방문 여부 체크
(0, 0 #20, VISITED) (0, 1 #20 , VISITED) (0, 2 #20 , VISITED)
(1, 0 #20, VISITED) (1, 1 #20 , VISITED) (1, 2 #20 , VISITED)
(2, 0 #40) (2, 1 #20, VISITED) (2, 2 #10)
두 번째 BFS 탐색의 시작은 방문하지 않은 나라 중 가장 빠른 (3, 1) 부터 탐색이 시작될 것이다.
두 번째 연합
(1, 2 #20)
|
(2, 1 #20) - (2, 2 #10)
인구 이동
(1, 2 #16)
|
(2, 1 #16) - (2, 2 #16)
최종 결과 : 더 이상 연합이 불가능하므로 종료
(0, 0 #20) (0, 1 #20) (0, 2 #20)
(1, 0 #20) (1, 1 #20) (1, 2 #16)
(2, 0 #40) (2, 1 #16) (2, 2 #16)
정리
- 2차원 배열의 탐색 문제 -> 그래프
- 입력 값을 배열 형태의 그래프로 표현
- 인접한 나라들을 탐색하기 위해 BFS 알고리즘 이용
- 첫 번째 연합 결과 = 인구 이동
- 연합의 횟수 = 인구 이동의 횟수
연합 > 인구 이동 > 연합한 나라들의 인구 수를 재계산 > 인구 이동이 불가능 할 때 까지 반복
구현
class Country {
private int x;
private int y;
public Country(int x, int y) {
this.x = x;
this.y = y;
}
public int getX() {
return x;
}
public int getY() {
return y;
}
}
public class Main {
private static int N;
private static int L;
private static int R;
private static int[][] graph; // (x, y) 나라, 저장된 값은 인구수
private static boolean[][] visited; // 방문 처리 여부
private static List<Country> unitedCountries; // 연합된 나라들
private static int unitedCount = 0; // 연합한 나라의 개수
private static int sumOfPopulationInUnitedCountry = 0; // 연합한 나라들의 인구수 합
private static int answer = 0; // 인구 이동이 일어난 횟수
// 상하좌우 : 인접한 나라를 판단하기 위함
private static int[] dx = {-1, 1, 0, 0};
private static int[] dy = {0, 0, 1, -1};
public static void main(String[] args) {
input();
solution();
System.out.println(answer);
}
private static void input() {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
L = sc.nextInt();
R = sc.nextInt();
// 그래프, 방문처리여부 초기화
graph = new int[N][N];
// 인구수 저장
for (int i = 0; i < N; i++) {
for (int k = 0; k < N; k++) {
graph[i][k] = sc.nextInt();
}
}
}
// 인구이동이 발생하지 않을 때 까지 반복
private static void solution() {
while(true) {
boolean isMoved = false;
visited = new boolean[N][N];
for (int x = 0; x < N; x++) {
for (int y = 0; y < N; y++) {
if(!visited[x][y]) { // uniteByBfs 를 통해 방문처리 된 인접리스트들에 대해서도 생략
unite(x, y);
if(unitedCountries.size() > 1) {
move();
answer++;
isMoved = true;
}
}
}
}
if(!isMoved) {
break;
}
}
}
private static void unite(int x, int y) {
Queue<Country> Q = new LinkedList<>();
unitedCountries = new ArrayList<>();
Country start = new Country(x, y);
Q.offer(start);
unitedCountries.add(start);
visited[x][y] = true;
// 연합한 나라의 개수 : 자기 자신으로 초기화
unitedCount = 1;
// 연합한 나라의 인구수 합 탐색 대상인 나라의 인구수로 초기화
sumOfPopulationInUnitedCountry = graph[x][y];
while(!Q.isEmpty()) {
Country country = Q.poll();
x = country.getX();
y = country.getY();
int p1 = graph[x][y];
// 상하좌우 탐색
for (int i = 0; i < dx.length; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if((nx >= 0 && ny >= 0 && nx < N && ny < N) && !visited[nx][ny]) {
int p2 = graph[nx][ny];
if(isLinkable(p1, p2)) {
Country adjacentCountry = new Country(nx, ny);
// 연결 가능한 인접한 나라를 Q 에 넣는다.
Q.offer(adjacentCountry);
// 연합한 나라를 보관하는 리스트에 넣는다.
unitedCountries.add(adjacentCountry);
// 연합한 나라의 인구수 합 누적
sumOfPopulationInUnitedCountry += p2;
// 연합한 나라의 개수 증가
unitedCount++;
// 방문 처리
visited[nx][ny] = true;
}
}
}
}
}
// 연결 가능한지
private static boolean isLinkable(int p1, int p2) {
int absValue = Math.abs(p1 - p2);
return L <= absValue && absValue <= R;
}
// 인구 이동, 연합한 나라들의 인구수를 재계산
private static void move() {
for(Country country : unitedCountries) {
graph[country.getX()][country.getY()] = sumOfPopulationInUnitedCountry / unitedCount;
}
}
}
728x90
'Algorithms > 문제 풀이' 카테고리의 다른 글
[BOJ 14502] 연구소 (0) | 2022.01.06 |
---|---|
[BOJ 15686] 치킨 배달 (0) | 2022.01.03 |
[BOJ 1715] 카드 정렬하기 (0) | 2021.12.18 |
[BOJ 18352] 특정 거리의 도시 찾기 (0) | 2021.12.18 |
[BOJ 3190] 뱀 (0) | 2021.12.18 |