#문제
레벨: G4
알고리즘: bfs
풀이시간: 40분
힌트 참조 유무:
https://www.acmicpc.net/problem/16234
#문제 풀이
특정 국가(A)를 기준점으로 삼고 그 국가와 연할될 수 있는 국가(B)를 찾고 B와 연합될 수 있는 국가를 찾고(C) 반복한다. 이 형식 어디서 보지 않았는가? 4방향+bfs(or dfs)이다. 그런데 bfs 한 번으로 모든 국가를 다 탐색할 수는 없다. 그래서 이중 for문으로 모든 국가를 돌면서 visited =false(방문하지 않은) 곳만 bfs를 돌린다. bfs 기본 문제이기 때문에 별다른 설명하지 않고 넘어가겠다.
#풀이 코드
import java.util.*;
import java.io.*;
public class Main {
static int N, L, R;
static int[][] A;
static boolean[][] visited;
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
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());
}
}
System.out.println(solution());
}
static int solution() {
int days = 0;
while (true) {
visited = new boolean[N][N];
boolean moved = false;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (!visited[i][j]) {
int population = bfs(i, j);
if (population > 1) moved = true;
}
}
}
if (!moved) return days;
days++;
}
}
static int bfs(int x, int y) {
Queue<int[]> queue = new LinkedList<>();
List<int[]> united = new ArrayList<>();
queue.offer(new int[]{x, y});
united.add(new int[]{x, y});
visited[x][y] = true;
int total = A[x][y];
int count = 1;
while (!queue.isEmpty()) {
int[] current = queue.poll();
for (int i = 0; i < 4; i++) {
int nx = current[0] + dx[i];
int ny = current[1] + dy[i];
if (nx >= 0 && nx < N && ny >= 0 && ny < N && !visited[nx][ny]) {
int diff = Math.abs(A[current[0]][current[1]] - A[nx][ny]);
if (diff >= L && diff <= R) {
queue.offer(new int[]{nx, ny});
united.add(new int[]{nx, ny});
visited[nx][ny] = true;
total += A[nx][ny];
count++;
}
}
}
}
int newPopulation = total / count;
for (int[] pos : united) {
A[pos[0]][pos[1]] = newPopulation;
}
return count;
}
}
'알고리즘 > BFS' 카테고리의 다른 글
[백준 9328] 열쇠 / 자바 / bfs + 구현 (0) | 2024.09.10 |
---|---|
[백준 16930] 달리기 / 자바 / bfs + dp (0) | 2024.08.13 |
[백준 4803] 트리 / 자바 / bfs (0) | 2024.07.26 |
[백준 16946] 벽 부수고 이동하기4 / 자바 / bfs or dfs(방향탐색) (3) | 2024.07.24 |
[백준 2638] 자바 / 치즈 / bfs (2) | 2024.07.23 |