[BOJ 16234] 인구 이동 (Java, BFS, 구현)알고리즘/그래프 탐색2023. 6. 14. 17:26
Table of Contents
반응형
문제 링크
https://www.acmicpc.net/problem/16234
풀이
- 격자형 그래프 탐색 문제
- BFS 풀이
- N이 최대 50이므로 O(N^2)으로 풀이 가능
예제 입력 4
3 5 10
10 15 20
20 30 25
40 22 10
예제 출력 4
2
1회차
int[][] WORLD
10 | 15 | 20 |
20 | 30 | 25 |
40 | 22 | 10 |
int[][] GROUP_INFO
0 | 0 | 0 |
0 | 0 | 0 |
1 | 0 | 2 |
1회차 인구 이동 결과
20 | 20 | 20 |
20 | 20 | 20 |
40 | 20 |
10 |
2회차
int[][] WORLD
20 | 20 | 20 |
20 | 20 | 20 |
40 | 20 |
10 |
int[][] GROUP_INFO
0 | 1 | 2 |
3 | 4 | 5 |
6 | 5 | 5 |
2회차 인구 이동 결과
20 | 20 | 20 |
20 | 20 | 16 |
40 | 16 |
16 |
그리고 마지막 조회시 GROUP_INFO 는 아래와 같이 되고, groupNumber = 9 가 되어 종료
0 | 1 | 2 |
3 | 4 | 5 |
6 | 7 | 8 |
제출 코드
import java.util.*;
import java.io.*;
public class Main {
static int N, L, R;
static int[][] WORLD, GROUP_INFO;
static int[][] DIRECTION = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
static void input() throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken()); // N * N 크기의 땅
L = Integer.parseInt(st.nextToken());
R = Integer.parseInt(st.nextToken());
GROUP_INFO = new int[N + 1][N + 1];
WORLD = new int[N + 1][N + 1];
for(int r = 1; r <= N; r++) {
st = new StringTokenizer(br.readLine());
for(int c = 1; c <= N; c++) {
WORLD[r][c] = Integer.parseInt(st.nextToken());
}
}
br.close();
}
static class Country {
int x;
int y;
public Country(int x, int y) {
this.x = x;
this.y = y;
}
}
static void bfs(int startX, int startY, int groupNumber) {
Queue<Country> que = new LinkedList<>();
que.add(new Country(startX, startY));
GROUP_INFO[startX][startY] = groupNumber;
List<Country> union = new ArrayList<>();
union.add(new Country(startX, startY));
int cnt = 1;
int sum = WORLD[startX][startY];
while(!que.isEmpty()) {
Country c = que.poll();
int x = c.x;
int y = c.y;
for(int i = 0; i < 4; i++) {
int nx = x + DIRECTION[i][0];
int ny = y + DIRECTION[i][1];
if(nx < 1 || ny < 1 || nx > N || ny > N) continue;
if(GROUP_INFO[nx][ny] != -1) continue;
int diff = Math.abs(WORLD[x][y] - WORLD[nx][ny]);
if(L <= diff && diff <= R) {
GROUP_INFO[nx][ny] = groupNumber;
que.add(new Country(nx, ny));
union.add(new Country(nx, ny));
cnt += 1;
sum += WORLD[nx][ny];
}
}
}
int avg = sum / cnt;
for(Country c : union) {
WORLD[c.x][c.y] = avg;
}
}
static void initGroupInfo() {
for(int i = 1; i <= N; i++) {
for(int j = 1; j <= N; j++) {
GROUP_INFO[i][j] = -1;
}
}
}
static void pro() {
int days = 0;
while(true) {
initGroupInfo();
int groupNumber = 0;
for(int i = 1; i <= N; i++) {
for(int j = 1; j <= N; j++) {
if(GROUP_INFO[i][j] == -1) {
bfs(i, j, groupNumber);
groupNumber += 1;
}
}
}
if(groupNumber == N * N) break;
else days += 1;
}
System.out.println(days);
}
public static void main(String[] args) throws Exception {
input();
pro();
}
}
반응형
'알고리즘 > 그래프 탐색' 카테고리의 다른 글
[BOJ 2636] 치즈 (Java, BFS) (0) | 2023.06.15 |
---|---|
[BOJ 3190] 뱀 (Java, BFS, 구현) (0) | 2023.06.14 |
[BOJ 2638] 치즈 (Java, BFS) (0) | 2023.06.14 |
[BOJ 9466] 텀 프로젝트 (Java, DFS) (0) | 2023.06.14 |
[BOJ 2668] 숫자고르기 (Java, DFS) (0) | 2023.06.14 |
@leejinwoo1126 :: 천천히 하나씩
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!