白駿16234号:人口移転
28682 ワード
問題の説明
方法
pseudocode
Main(){
while(flag){
v = new boolean[N][N]; // day가 바뀔때마다 방문을 초기화해야 합니다.
for(모든 행){
for(모든 열){
if(해당 국가를 아직 방문하지 않았다면){
if(BFS){ // BFS는 Union이 형성되었는지 확인하는 코드입니다.
// 현재의 day에 Union이 실행되지 않을 때까지 while문이 진행됩니다.
// 하지만 !BFS면 flag=false는 올바르지 못한 코드입니다.
// 예를들어 (0,0)국가는 아무런 Union이 없고, (0,1),(1,0),(1,1)이 Union인 경우 문제가 발생합니다.
flag = true // 하나라도 Union이 일어났다면 while문을 끝내지 않습니다.
}
}
}
}
}
}
BFS(){
while(q가 빌 때 까지){
temp = q.poll();
temp를 Union에 넣습니다.
for(4방탐색을 진행하면서){
if(해당 방향으로 국가가 존재하며(board를 벗어나지 않으며),그 국가를 아직 방문하지 않았고,
temp국가와 인접국가의 인구 차이가 L이상 R이하면){
q에 해당 국가를 넣습니다.
해당 국가를 방문처리 합니다.
}
}
}
if(해당 국가와 연합된 국가가 하나도 없다면){
return false;
}else{ // 해당 국가와 연합이 형성된 국가들이 있다면
연합은 인구를 나눠가집니다.
return true;
}
}
正解
import java.util.*;
public class Main {
static int N, L, R;
static int[] dx = { 0, 1, -1, 0 };
static int[] dy = { 1, 0, 0, -1 };
static int[][] board;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
L = sc.nextInt();
R = sc.nextInt();
board = new int[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
board[i][j] = sc.nextInt();
}
}
int day = 0;
boolean flag = true;
while (flag) {
flag = false;
day++;
boolean[][] v = new boolean[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (!v[i][j]) {
int[] temp = { i, j };
if (BFS(temp, v)) { // 해당 국가에서 국경이 개방되는 국가가 존재한다면 한번 더 while이 실행될 수 있습니다.
flag = true;
}
}
}
}
}
System.out.println(day - 1);
}
public static boolean BFS(int[] start, boolean[][] v) {
Queue<int[]> q = new LinkedList<int[]>();
List<int[]> Union = new ArrayList<int[]>();
q.add(start);
v[start[0]][start[1]] = true;
while (!q.isEmpty()) {
int[] temp = q.poll();
Union.add(temp);
for (int d = 0; d < 4; d++) {
int nx = temp[0] + dx[d];
int ny = temp[1] + dy[d];
if (0 <= nx && nx < N && 0 <= ny && ny < N && !v[nx][ny]
&& L <= Math.abs(board[temp[0]][temp[1]] - board[nx][ny])
&& Math.abs(board[temp[0]][temp[1]] - board[nx][ny]) <= R) {
v[nx][ny] = true;
int[] temp2 = { nx, ny };
q.add(temp2);
}
}
}
int cnt = Union.size();
int Sum = 0;
if (cnt == 1) { // BFS를 시작한 국가만 Union에 포함된다는 건 곧 아무런 이동도 없다는 의미입니다.
return false;
} else {
for (int i = 0; i < cnt; i++) {
int[] pos = Union.get(i);
Sum += board[pos[0]][pos[1]];
}
for (int i = 0; i < cnt; i++) {
int[] pos = Union.get(i);
board[pos[0]][pos[1]] = Sum / cnt;
}
return true;
}
}
}
その他
これは
Reference
この問題について(白駿16234号:人口移転), 我々は、より多くの情報をここで見つけました https://velog.io/@qwerty1434/백준-16234번-인구-이동テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol