https://www.acmicpc.net/problem/16234
16234번: 인구 이동
N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모
www.acmicpc.net
[정답 코드]
import java.io.*;
import java.util.*;
public class Main {
static int[][] graph;
static boolean[][] visited;
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1}; // 상하좌우순서
static int N, L ,R;
static ArrayList<int[]> list;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
L = Integer.parseInt(st.nextToken());
R = Integer.parseInt(st.nextToken());
graph = new int[N][N];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine(), " ");
for (int j = 0; j < N; j++) {
graph[i][j] = Integer.parseInt(st.nextToken());
}
}
System.out.println(move());
}
public static int move() { // 더이상 인구 이동이 일어나지 않을때 까지 반복
int result = 0;
while (true) {
boolean isMove = false;
visited = new boolean[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (!visited[i][j]) {
int sum = dfs(i, j); // 방문하지 않은 곳 dfs 탐색
if (list.size() > 1) {
changePopulation(sum); // 국경이 열린 노드끼리 인구 이동
isMove = true;
}
}
}
}
if (!isMove) {
return result;
}
result++;
}
}
public static void changePopulation(int sum) {
int avg = sum / list.size();
for (int i = 0; i < list.size(); i++) {
int x = list.get(i)[0];
int y = list.get(i)[1];
graph[x][y] = avg;
}
}
public static int dfs(int x, int y) {
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{x, y});
list = new ArrayList<>();
list.add(new int[]{x, y});
visited[x][y] = true;
int sum = graph[x][y];
while (!queue.isEmpty()) {
int tmp[] = queue.poll();
for (int i = 0; i < 4; i++) { // 4방탐색
int nx = tmp[0] + dx[i];
int ny = tmp[1] + dy[i];
if (nx >= 0 && nx < N && ny >= 0 && ny < N) { // graph 범위 내
// 방문한적 없고, L과 R 사이일 때
if (!visited[nx][ny] && L <= Math.abs(graph[tmp[0]][tmp[1]] - graph[nx][ny]) && Math.abs(graph[tmp[0]][tmp[1]] - graph[nx][ny]) <= R) {
visited[nx][ny] = true; // 방문한곳으로 변경
queue.offer(new int[]{nx, ny}); // 새로 큐에 담아줌
list.add(new int[]{nx, ny}); // 연결된 나라끼리는 따로 좌표를 담아줌
sum += graph[nx][ny];
}
}
}
}
return sum;
}
}
[설명]
dfs와 구현을 동시에 해야하는 문제이다.
문제를 세분화해서 풀어야 한다.
1. 순회를하며 방문하지 않은 노드를방문한다. 모든 노드를방문할 때 까지 반복된다.
2. 방문한 노드에서 dfs 알고리즘을 구현.
- dfs 알고리즘 : 연결된 노드들의 좌표를 list에 담아줌. 연결된 노드들의 값을 모두 더함.
3. 연결된 것 노드의 체크가 끝나면 인구 이동을 시작.
- 인구이동 로직 : 연결된 노드들의 좌표를 담았던 list를 하나씩 꺼내며 연결된 노드들의 값을 모드 더했던것을 적절히 나눠 값을 배분
4. 모든 노드들을 방문했다면 1일 증가
5. 1 ~ 5를 반복, 인구이동이 더이상 일어나지 않을 때 까지 반복
'코딩테스트' 카테고리의 다른 글
| 백준 1068번: 트리[JAVA] (1) | 2024.03.15 |
|---|---|
| 백준 1991번: 트리 순회[JAVA] (1) | 2024.03.15 |
| 백준 2493번: 탑[JAVA] (0) | 2024.03.12 |
| 백준 7682번: 틱택토[JAVA] (0) | 2024.03.11 |
| 백준 9372번: 상근이의 여행[JAVA] (0) | 2024.03.09 |
