https://www.acmicpc.net/problem/16234
16234번: 인구 이동
N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모
www.acmicpc.net
오늘부터는 본격적으로 코딩테스트를 준비하기 위해서 그래프 탐색문제를 집중적으로 풀이해보려 한다. 오늘 풀이해볼 문제는 골드5문제로 너비우선 탐색을 이용해서 구현을 하는 문제이다. 문제만 보면 조금 복잡해 보일 수 있지만, 예시에 친절하게 나와있기 때문에, 인구이동이 일어나는 날에 필요한 작업을 해주고, 최종적으로 인구이동이 일어난 날을 반환하는 것이다. 천천히 단계적으로 풀이를 해보겠다.
[ 1. 문제 분석 ]
예제에 나와 있는 내용은 인구이동이 하루만 일어난 날을 기준으로 보여줬다. 그 이상은 응용을 하라는 뜻 일텐데, 인구이동이 2일 동안 일어나는 예제 입력 4를 보자
기본적으로 아래와 같은 map으로 시작을 할 것이다.
이제 순차적으로 BFS탐색을 진행하면서 인접한 노드 간에 인구수 차이가 L(5)과 R(10)사이인 인구는 국경선을 열어주자. 한 번의 탐색을 하면 아래와 같은 결과가 도출된다.
이제 국경이 열린 나라끼리는 "연합"을 맺게 되고, 연합을 맺은 국가는 같은 수의 인구가 거주하도록 인구가 이동한다. 연합국가의 인구수는 총 10 + 15 + 20 + 20 + 30 + 25 + 22 = 142명이다. 이를 7로 나누게 되면 20.xxx가 나오는데 소수점 밑은 버리라고 했으므로 연합국가의 인구수는 20으로 변경한다.
이제 여기서 다시 한 번 BFS탐색을 해야한다. 실제 코드로 구현하는 경우에는 반복을 어떻게 탈출해야 할지를 고민해야 한다. 처음과 같은 방법으로 인접한 노드 간에 인구수 차이가 L(5)과 R(10)사이인 국가는 국경선을 열여주면 아래와 같다.
연합 국가의 인구수를 모두 더하면 20 + 20 + 10 = 50이고 이를 3으로 나누면 16.xxx인데 소수점 밑을 버린 값 16으로 인구수를 바꾸어 준다.
결과적으로 위와 같은 인구 분포가 완성이 되며 이제는 더 이상 인접한 국가의 인구 수 차이가 5이상 10이하를 만족하지 않기 때문에 인구이동을 중지한다. 총 2일의 인구이동이 있었기 때문에 2를 결과로 출력한다.
[ 2. 단계적 소스코드 ]
1. 변수 초기화
문제에서 주어진 입력 정보를 수신해서 map을 구성하고, 메서드를 시작한다. 이때 편의상 자료구조와 변수는 static으로 전역변수화 시켰다. 소스 코드만 보면 일반적으로 보던 너비우선 탐색 틀과 비슷하기에 추가 설명은 하지 않겠다. List는 연합국가의 (x, y)좌푯값을 저장해줄 자료구조이라는 것만 알고 넘어가자.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
static int []dx = {-1, 1, 0, 0};
static int []dy = { 0, 0, -1, 1};
static List<nnode> list;
static int map[][];
static boolean visit[][];
static int n, L, R;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
//차이의 최소(L), 최대(R)
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());
}
}
int day = move();
System.out.println(day);
}
|
cs |
2. 인구 이동. move()
모든 노드에 대해서 방문 여부를 체크해본다. 모든 그래프가 연결되어 있다는 보장이 없다.(모든 국가가 연합일 것이라는 보장이 없다는 것이다.) 따라서 모든 노드에 대해서 bfs탐색을 해주는데, 탐색을 하는 자세한 과정은 아래에서 설명하겠다.
탐색의 결과로 연합 국가의 총 인구수를 반환한다는 점만 알고 넘어가도록 하자. isMove는 인구 이동이 일어났으면 True, 아니면 False로 처리하여 무한 루프를 탈출할 수 있는 조건을 생성해준 것이다.
리스트의 사이즈 즉, 요소의 개수가 무엇을 의미할까? 맞다 연합한 국가의 수이다. 이 값이 1이라면 연합한 국가 없이 처음 탐색을 출발한 출발 국가만 포함되어 있다는 뜻이다. 그러므로 리스트의 요소 개수가 1보다 큰 경우가 연합국가가 있다는 뜻이고, 인구이동이 일어난다는 말이 된다. 이를 사용해 무한 루프를 탈출하자.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
private static int move() {//더 이상 인구이동이 일어나지 않을 때까지 반복한다.
// TODO Auto-generated method stub
int res = 0;
while(true) {
boolean isMove = false;
visit = new boolean[n][n];
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
if(!visit[i][j]) {//아직 방문하지 않았다면
int sum = bfs(i,j);//탐색을 통해서 국경선이 열린 국가는 연합으로 취급하고 원래 있던 인구수의 누적합을 구한다.
if(list.size() > 1) {//연합이 하나라도 존재한다면
changeMap(sum);
isMove = true;
}
}
}
}
//인구 이동이 일어나지 않았다면,,,
if(!isMove) return res;
//인구 이동이 일어났다면,,,
res++;
}
}
|
cs |
3. 연합 국가 찾기 bfs(i, j)
탐색을 진행하면서 배열 인덱스를 벗어나거나, 이미 방문한 노드에 대해서는 가차없이 skip한다. 한가지 주의할 점은 두 국가의 인구 수 차이를 저장하는 tmp변수를 인덱스 조건을 검사한 후에 진행해야 indexoutexception이 발생하지 않는다.
조건을 모두 만족한다면, 해당 노드(국가)를 다음 노드 탐색을 위해 큐에 넣고, 연합 국가를 인식하기 위해 리스트에 넣는다. 위에서 말한대로 bfs 탐색의 반환값이 총 연합국가의 인구수라고 했기 때문에 조건을 만족하는 국가의 인구수를 누적으로 더해줘야 한다.
sum의 초깃값으로는 BFS탐색을 시작한 국가의 인구수로 초기화한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
private static int bfs(int x, int y) {
// TODO Auto-generated method stub
Queue<nnode> q = new LinkedList<>();
list = new ArrayList<nnode>();
visit[x][y] = true;
q.add(new nnode(x, y));
list.add(new nnode(x, y));
int sum = map[x][y];
while(!q.isEmpty()) {
nnode now = q.poll();
for(int k=0; k<4; k++) {
int xx = now.x + dx[k];
int yy = now.y + dy[k];
//인덱스 범위를 벗어나거나 이미 방문했다면 스킵
if(xx < 0 || yy < 0 || xx >= n || yy >= n || visit[xx][yy]) continue;
int tmp = Math.abs(map[now.x][now.y] - map[xx][yy]);
if(tmp >= L && tmp <= R) {
//연합한 전체 나라의 수
visit[xx][yy] = true;
q.add(new nnode(xx, yy));
list.add(new nnode(xx, yy));
sum += map[xx][yy];
}
}
}
return sum;
}
|
cs |
4. map 갱신changeMap()
연합 국가끼리는 같은 수의 인구수가 거주한다고 했기 때문에 인구수를 갱신해주는 작업을 해야하는데, sum값을 리스트의 요소개수(연합 국가 수)로 나눈 값을 리스트에 저장된 좌표에 있는 모든 곳에 갱신해준다. 이 후에는 이 갱싱된 값을 기준으로 다시 연합국가가 생성될 수 있는지 검사할 것이다.
|
1
2
3
4
5
6
7
|
private static void changeMap(int sum) {
// TODO Auto-generated method stub
int avg = sum / list.size(); //int형을 사용해 몫연산을 진행한다.
for(nnode n : list) {
map[n.x][n.y] = avg;
}
}
|
cs |
[ 3. 전체 코드 ]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
|
package BFS;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
public class _16234_인구이동 {
static int []dx = {-1, 1, 0, 0};
static int []dy = { 0, 0, -1, 1};
static List<nnode> list;
static int map[][];
static boolean visit[][];
static int n, L, R;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
//차이의 최소(L), 최대(R)
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());
}
}
int day = move();
System.out.println(day);
}
private static int move() {//더 이상 인구이동이 일어나지 않을 때까지 반복한다.
// TODO Auto-generated method stub
int res = 0;
while(true) {
boolean isMove = false;
visit = new boolean[n][n];
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
if(!visit[i][j]) {//아직 방문하지 않았다면
int sum = bfs(i,j);//탐색을 통해서 국경선이 열린 국가는 연합으로 취급하고 원래 있던 인구수의 누적합을 구한다.
if(list.size() > 1) {//연합이 하나라도 존재한다면
changeMap(sum);
isMove = true;
}
}
}
}
//인구 이동이 일어나지 않았다면,,,
if(!isMove) return res;
//인구 이동이 일어났다면,,,
res++;
}
}
private static void changeMap(int sum) {
// TODO Auto-generated method stub
int avg = sum / list.size(); //int형을 사용해 몫연산을 진행한다.
for(nnode n : list) {
map[n.x][n.y] = avg;
}
}
private static int bfs(int x, int y) {
// TODO Auto-generated method stub
Queue<nnode> q = new LinkedList<>();
list = new ArrayList<nnode>();
visit[x][y] = true;
q.add(new nnode(x, y));
list.add(new nnode(x, y));
int sum = map[x][y];
while(!q.isEmpty()) {
nnode now = q.poll();
for(int k=0; k<4; k++) {
int xx = now.x + dx[k];
int yy = now.y + dy[k];
//인덱스 범위를 벗어나거나 이미 방문했다면 스킵
if(xx < 0 || yy < 0 || xx >= n || yy >= n || visit[xx][yy]) continue;
int tmp = Math.abs(map[now.x][now.y] - map[xx][yy]);
if(tmp >= L && tmp <= R) {
//연합한 전체 나라의 수
visit[xx][yy] = true;
q.add(new nnode(xx, yy));
list.add(new nnode(xx, yy));
sum += map[xx][yy];
}
}
}
return sum;
}
}
class nnode{
int x, y;
public nnode(int x, int y) {
super();
this.x = x;
this.y = y;
}
}
|
cs |
'알고리즘 > 백준[문제풀이]' 카테고리의 다른 글
| BFS_5547_일루미네이션_육각행렬 (0) | 2022.07.04 |
|---|---|
| BFS_16236_아기상어 (0) | 2022.06.29 |
| 위상정렬_2252_줄세우기 (0) | 2022.06.22 |
| 백준[자바]_분할정복_1780_종이의 개수 (0) | 2022.06.20 |
| 백준[자바]_11279_1927_우선순위큐 (0) | 2022.06.17 |
