내 코드
package com.company;
import java.io.*;
import java.util.*;
public class Main {
static int[][] d = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
static int[][] arr;
static int R, L, N, count;
static int[][] visited;
static int[] ck;
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());
arr = new int[N][N];
ck = new int[N * N + 1];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
int check = 0; // 연합 번호
int day = 0; // 일수
while (true) {
check = 0;
visited = new int[N][N]; // 각 나라의 연합번호
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (visited[i][j] == 0) {
count = 0; // 연합 수
check++;
int total = dfs(i, j, check); // 연합에 있는 나라 수와 총 인구수 가져옴
ck[check] = total / count; // (인구 수 / 나라 수)를 연합 번호에 저장
}
}
}
// 연합 수와 나라 수가 같으면 종료
if (check == N * N) {
break;
}
// 각 나라의 연합 번호에 맞게 인구수를 바꿈
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
arr[i][j] = ck[visited[i][j]];
}
}
day++;
}
System.out.println(day);
}
static int dfs(int x, int y, int check) {
count++;
int p = arr[x][y]; // 반환할 인구수
visited[x][y] = check; // 나라의 연합 번호
for (int i = 0; i < 4; i++) {
int nextX = d[i][0] + x;
int nextY = d[i][1] + y;
if (nextX >= 0 && nextY >= 0 && nextX < N && nextY < N && visited[nextX][nextY] == 0) {
int differ = Math.abs(arr[x][y] - arr[nextX][nextY]);
if (differ >= L && differ <= R) { // 조건
p += dfs(nextX, nextY, check);
}
}
}
return p;
}
}
'코딩테스트 > [백준] 코딩테스트 연습' 카테고리의 다른 글
사다리 조작 - 15684번 (0) | 2022.04.05 |
---|---|
톱니바퀴 - 14891번 (0) | 2022.04.04 |
녹색 옷 입은 애가 젤다지? - 4485번 (0) | 2022.04.01 |
달이 차오른다, 가자. - 1194번 (0) | 2022.04.01 |
백조의 호수 - 3197번 (0) | 2022.03.31 |