백준 16234 인구 이동
**아이디어
- 처음에 bfs로 했을때 안풀림!!!
- 인구 이동이 발생하는 동안 while문으로 접근해서 이동이 발생하면, day추가하는 방식으로 함.
javapackage boj_gold.p16234_인구이동;
import java.io.*;
import java.util.*;
public class Review1 {
// 전역 변수 선언
static int[][] map; // N x N 크기의 땅 (각 칸의 인구수)
static boolean[][] visited; // BFS 방문 체크 배열
static int[] dx = {-1, 1, 0, 0}; // 상하좌우 x
static int[] dy = {0, 0, -1, 1}; // 상하좌우 y
static int N, L, R; // 입력 받기
static boolean isMoved; // 인구 이동 발생 여부 플래그
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());
// 맵 초기화 및 입력
map = new int[N][N];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
int day = 0; // 인구 이동이 며칠 동안 발생하는지 카운트
// 인구 이동이 없을 때까지 반복
while (true) {
// 매일 visited 배열 초기화
visited = new boolean[N][N];
// 이동 발생 여부 초기화 (false부터 시작)
isMoved = false;
// 전체 맵을 순회하면서 연합 찾기
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
// 아직 방문하지 않은 칸이면 BFS로 연합 찾기
if (!visited[i][j]) {
bfs(i, j);
}
}
}
// 인구 이동이 발생했으면 day 증가
if (isMoved) {
day++;
} else {
// 인구 이동이 발생하지 않았으면 종료
break;
}
}
// 결과 출력 (인구 이동이 며칠 동안 발생했는지)
System.out.println(day);
}
/**
* BFS를 이용해 (x, y)에서 시작하는 연합을 찾고 인구 이동 처리
*/
static void bfs(int x, int y) {
Queue<int[]> q = new ArrayDeque<>(); // BFS 탐색용 큐
List<int[]> union = new ArrayList<>(); // 연합에 속한 칸들을 저장
// 시작 칸을 큐와 연합에 추가
q.offer(new int[]{x, y});
union.add(new int[]{x, y});
visited[x][y] = true;
int sum = map[x][y]; // 연합의 총 인구수 (시작 칸의 인구수로 초기화)
// BFS 탐색 시작
while (!q.isEmpty()) {
int[] cur = q.poll();
int cx = cur[0]; // 현재 x 좌표
int cy = cur[1]; // 현재 y 좌표
// 상하좌우 4방향 탐색
for (int i = 0; i < 4; i++) {
int nx = cx + dx[i]; // 다음 x 좌표
int ny = cy + dy[i]; // 다음 y 좌표
// 경계 체크 및 방문 체크
if (0 <= nx && nx < N && 0 <= ny && ny < N && !visited[nx][ny]) {
// 현재 칸과 다음 칸의 인구 차이 계산
int diff = Math.abs(map[cx][cy] - map[nx][ny]);
// 인구 차이가 L 이상 R 이하이면 연합 형성 가능
if (diff >= L && diff <= R) {
q.offer(new int[]{nx, ny}); // 큐에 추가 (BFS 계속)
union.add(new int[]{nx, ny}); // 연합에 추가
visited[nx][ny] = true; // 방문 처리
sum += map[nx][ny]; // 연합의 총 인구수에 더하기
}
}
}
}
// 연합이 2개 이상의 칸으로 이루어진 경우에만 인구 이동 발생
if (union.size() >= 2) {
// 연합의 평균 인구수 계산
int avg = sum / union.size();
// 연합에 속한 모든 칸의 인구수를 평균값으로 업데이트
for (int[] pos : union) {
map[pos[0]][pos[1]] = avg;
}
// 인구 이동이 발생했음을 표시
isMoved = true;
}
}
}
package boj_gold.p16234_인구이동;
//인구 이동이 얼마나 걸리는지 .
//인구이동이 일어나는 조건: 두 나라의 인구 차이가 L명 R명 이하 ->
//visited[] -> bfs 사용
// 방향 둘러가면서, 차이가 L, R 사이면 -> bfs 호출 -> count + 1
// 인구 이동 안하면 바로 0 출력 -> return
//count 출력
import java.io.*;
import java.util.*;
public class Review1 {
static int[][] map;
static boolean[][] visited;
static int[] dx = {-1, 1, 0,0};
static int[] dy = {0,0,-1,1};
static int N, L, R;
static Queue<int[]> q;
static boolean isMoved;
static int sum;
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());
map = new int[N][N];
//
for (int i = 0; i< N; i++){
st = new StringTokenizer(br.readLine());
for (int j =0; j<N; j++){
map[i][j] = Integer.parseInt(st.nextToken());
}
}
int day = 0;
//인구이동이 발생하는 동안
while(isMoved) {
//visited 초기화
visited = new boolean[N][N];
//이동 발생 여부
isMoved = false;
//전체 맵 순회하면서
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (!visited[i][j]) {
//bfs로 연합 찾기
bfs(i, j);
isMoved = true;
}
}
}//for
//만약 이동이 발생하면
if(isMoved){
day++;
}else break;
}//while
System.out.println(day);
// System.out.println(Arrays.deepToString(map));
//일단 (0,0부터 시작하기)
//만약 호출을 안하면 넣어줘야 함...........
// int count =0;
// q = new ArrayDeque<>();
// for(int i = 0; i< N; i++){
// for (int j = 0; j< N; j++){
// if(!visited[i][j]){
// q.offer(new int[] {i,j});
// int sum = bfs(i, j, 0);
// count++;
// }
// }
// }
// System.out.println(count);
}//main
static void bfs(int x, int y){
//돌면서 찾기
Queue<int[]> q = new ArrayDeque<>();
//연합에 속한 칸 저장
List<int[]> union = new ArrayList<>();
q.offer(new int[]{x,y});
union.add(new int[]{x,y});
visited[x][y] = true;
while(!q.isEmpty()){
int[] cur = q.poll();
int cx = cur[0];
int cy = cur[1];
for(int i =0; i<4; i++){
//이동하면서 차이가 L, R사이이면,
int nx = cx+ dx[i];
int ny = cy + dy[i];
if (0<=nx && nx <N && 0<=ny && ny<N && !visited[nx][ny]){
int diff = Math.abs(map[cx][cy] - map[nx][ny]);
if (diff>=L && diff<=R){
//이동
q.offer(new int[]{nx,ny});
union.add(new int[]{nx,ny});
visited[nx][ny] = true;
sum += map[nx][ny];
//bfs(nx, ny, sum+map[cx][cy]);
}
}
}
}//while
//현재
//union이 2개이상이라면 ?
if(union.size()>1){
//평균 계산
int avg = sum/union.size();
for (int[] pos: union){
map[pos[0]][pos[1]] = avg;//map 업데이트
}
isMoved = true;
}
}
// static int bfs(int x, int y, int sum){
// q.offer(new int[] {x,y});
// visited[x][y] = true;
// //현재
// int[] cur = q.poll();
// int cx = cur[0];
// int cy = cur[1];
//
// cnt =0;
// for (int i = 0; i< 4; i++){
// //이동하면서 차이가 L이상 R이하라면, 일단 더함
// int nx = x+ dx[i];
// int ny = y+ dy[i];
// if (0<=nx && nx <N && 0<=ny && ny<N && !visited[nx][ny]){//경계선
// int diff = Math.abs(map[cx][cy] - map[nx][ny]);
// if (diff>=L && diff<=R){
// //이동
// bfs(nx, ny, sum + map[cx][cy]);
// cnt++;
// }
//
// }
// }//for
// return sum;
// }
}
따뜻한 시선으로 세상을 변화시키는 데이터사이언티스트