[BOJ 16234] ์ธ๊ตฌ์ด๋
1. ๋ฌธ์ : https://www.acmicpc.net/problem/1103
2. ํ์ด
list์ ๋ ธ๋๋ฅผ ๋ฃ์ด์ ๊ทธ ๋ ธ๋๋ง ๊ฐ์ ๋ณ๊ฒฝํด์ฃผ๋ ๋ฐฉ๋ฒ์ด ์์๋ค.
3. ์ฝ๋
package baekjoon;
import java.util.*;
public class Main {
static int n, l, r;
static int[][] board;
static boolean[][] visited;
static int[] dx = {0, 1, 0, -1};
static int[] dy = {1, 0, -1, 0};
static ArrayList<Node> list; //์ธ๊ตฌ ์ด๋์ด ํ์ํ ๋
ธ๋ ๋ฆฌ์คํธ
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
l = scan.nextInt();
r = scan.nextInt();
board = new int[n][n];
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
board[i][j] = scan.nextInt();
}
}
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 = bfs(i, j); //bfsํ์์ผ๋ก ์ด๋ฆด ์ ์๋ ๊ตญ๊ฒฝ์ ํ์ธ ํ๋ฉฐ ์ธ๊ตฌ ์ด๋ํ ์ด ์ธ๊ตฌ์ ๋ฐํ
if(list.size() > 1) {
changePopulation(sum); //์ด๋ฆฐ ๊ตญ๊ฒฝ์ ๋ด์ ๋
ธ๋๋ค ์ธ๊ตฌ ๋ณ๊ฒฝ
isMove = true;
}
}
}
}
if(!isMove) return result;;
result++;
}
}
public static int bfs(int x, int y) {
Queue<Node> q = new LinkedList<>();
list = new ArrayList<>();
q.offer(new Node(x, y));
list.add(new Node(x, y));
visited[x][y] = true;
int sum = board[x][y];
while(!q.isEmpty()) {
Node current = q.poll();
for(int i = 0; i < 4; i++) {
int nx = current.x + dx[i];
int ny = current.y + dy[i];
if(nx >= 0 && ny >= 0 && nx < n && ny < n && !visited[nx][ny]) {
int diff = Math.abs(board[current.x][current.y] - board[nx][ny]);
if(l <= diff && diff <= r) {
q.offer(new Node(nx, ny));
list.add(new Node(nx, ny));
sum += board[nx][ny];
visited[nx][ny] = true;
}
}
}
}
return sum;
}
public static void changePopulation(int sum) {
int avg = sum / list.size();
for(Node n : list) {
board[n.x][n.y] = avg;
}
}
public static class Node {
int x;
int y;
public Node(int x, int y) {
this.x = x;
this.y = y;
}
}
}
'๐ป Coding Problems Solving > DFS | BFS | Backtracking' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[BOJ 5427] ๋ถ (0) | 2023.08.24 |
---|---|
[BOJ 2206] ๋ฒฝ๋ถ์๊ณ ์ด๋ํ๊ธฐ (0) | 2023.08.21 |
[BOJ 1103] ์คํํธ๋งํฌ (0) | 2023.08.11 |
[BOJ 9466] ํ ํ๋ก์ ํธ (0) | 2023.08.01 |
[BOJ 2668] ์ซ์๊ณ ๋ฅด๊ธฐ (0) | 2023.06.27 |
์ต๊ทผ๋๊ธ