[백준] 16234번 인구 이동 JAVA (자바) 풀이

문제 16234(BFS)

 

 :  N×N크기의 땅

    각 땅에는 나라가 하나씩 존재 ( r행 c열에 있는 나라에는 A[r][c]명이 산다)

 

 :  인구 이동이 없을 때까지 지속된다.

• 붙어있는 두 나라의 인구 차이가 L명 이상, R명 이하라면 인구 이동 시작
• 인접한 칸만을 이용해 이동할 수 있으면 연합
• 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)
  편의상 소수점은 버린다
• 연합을 해체하고 모든 국경선을 닫기

 :  각 나라의 인구수가 주어졌을 때, 인구 이동이 며칠 동안 발생하는지 구하는 프로그램

 

 

[입력]

 :  첫째 줄에 N, L, R (1 ≤ N ≤ 50, 1 ≤ L ≤ R ≤ 100)

    둘째 줄부터 N개의 줄에 각 나라의 인구수

    r행 c열에 주어지는 정수는 A[r][c]의 값 (0 ≤ A[r][c] ≤ 100)

 

:  인구 이동이 발생하는 일수가 2,000번 보다 작거나 같은 입력만 주어진다

  

 

 [출력]

 :  인구 이동이 며칠 동안 발생하는지 첫째 줄에 출력

 

 

 

 [문제접근]

 

 

1. 시작지점 고정 후 큐에 집어넣기

 

 

보는 것과 같이 한 번에 인구이동 하는 영역이 떨어져 있을 수 있다

즉 시작 지점이 어디냐에 따라서 영역이 결정된다

그렇다면 bfs는 for문을 통해 시작지점을 이동해가며 수행한다 

 

 

 

 

 

 

2. 상하좌우로 이동 가능하니까 for문을 통해 next 지점 좌표 뽑아내기

• int nx = p[0] + dx[i], ny = p[1] + dy[i];

 

3. 조건1) 뽑아낸 좌표들이 배열 범위 안에 있으며 아직 방문하지 않았는지 체크

• if(0<=nx&&nx<N && 0<=ny&&ny<N && !visit[nx][ny])

 

4. 범위 안에 있다면 현위치와 next 지점 간의 거리 차이를 구한다

• 원래 같았으면 바로 큐에 추가하지만 거리 차이를 확인하는 조건도 있으므로 거리부터 계산
• int diff = Math.abs(arr[p[0]][p[1]]-arr[nx][ny]);
                    

5. 조건 2) 거리 차이가 L과 R사이에 있다면 큐에 추가

• if(L<=diff&&diff<=R)
• 방문 처리 후 큐에 추가 sum 객체에 누적합과 count 저장
• 어느 좌표들의 값을 바꿔야할 지 알아야 하므로 좌표값도 list에 저장

     

6. 모든 경로 탐색 후 sum/count 연산 후 해당 좌표들의 값 변경

• 위에서 저장한 좌표 값 하나씩 꺼내 arr배열값 sum/count로 변경

       

7. 평균값 계산 후 다음 날로 넘어간다 

• 평균값을 계산하고 평균값으로 arr배열이 갱신된 후 다음 이동할 영역 찾는 것은 while문부터 한 번 더 돌려서 찾는 것이다
  
  
• 입력이 아래와 같은 경우라면 
   3   5  10
  10 15 20
  20 30 25
  40 22 10 
  • 첫째날은 (main메서드의 while문 1회차)
    20 20 20
    20 20 20
    40 20 10 
    
    
  • 둘째날은 (main메서드의 while문 2회차)
    18 18 18
    18 18 18
    40 18 18 

 

 [코드]

import java.io.*;
import java.util.*;
public class Main{
    static int N,L,R,arr[][];
    static boolean visit[][];
    static int dx[] = {0,0,1,-1};
    static int dy[] = {1,-1,0,0};
    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];
        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 movecount = 0;
        while(true){
            boolean move = false;
            visit = new boolean[N][N];
            for(int i=0;i<N;i++){
                for(int j=0;j<N;j++){
                    if(!visit[i][j]&&bfs(i,j)){
                        move=true;
                    }
                }
            }
            if(!move){
                break;
            }
            movecount++;
        }
        System.out.println(movecount);
    }
    
    static boolean bfs(int x, int y){
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{x,y});
        visit[x][y]=true;
        int sum = arr[x][y];
        int count = 1;
        
        List<int[]> node = new ArrayList<>();
        node.add(new int[]{x,y});
       
        while(!q.isEmpty()){
            int p[] = q.poll();
            for(int i=0; i<4;i++){
                int nx = p[0] + dx[i], ny = p[1] + dy[i];
                if(0<=nx&&nx<N && 0<=ny&&ny<N && !visit[nx][ny]){
                    int diff = Math.abs(arr[p[0]][p[1]]-arr[nx][ny]);
                    if(L<=diff&&diff<=R){
                        visit[nx][ny]=true;
                        q.add(new int[]{nx,ny});
                        sum += arr[nx][ny];
                        count++;
                        node.add(new int[]{nx,ny});
                    }
                }
            }
        }
        
        if(count>1){
            int avg = sum/count;
            for(int[] n: node){
                arr[n[0]][n[1]] = avg;
            }
            return true;
        }
        return false;
    }
}

 

 [해설]
     

 :  static int N,L,R,arr[][];  
    static boolean visit[][];
    static int dx[] = {0,0,1,-1};
    static int dy[] = {1,-1,0,0};

 :  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    N = Integer.parseInt(st.nextToken());  입력 1
    L = Integer.parseInt(st.nextToken());  입력 2
    R = Integer.parseInt(st.nextToken());  입력 3
        
 :  arr = new int[N][N];  배열크기 초기화
    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 movecount = 0;  최종 출력할 결과
    while(true){  이전에 bfs 성공해서 move가 true였다면 이어서 반복
          boolean move = false;  처음엔 false로 초기화
          visit = new boolean[N][N];  방문 초기화
          for(int i=0;i<N;i++){
                for(int j=0;j<N;j++){   bfs 시작지점 순차적으로 돌리기
                    if(!visit[i][j]&&bfs(i,j)){  방문 확인 / bfs true인기 확인
                        move=true;  어느 시작지점에서의 bfs를 실행하는 동안은 true로 처리
                    }
                }
          }
          

          if(!move){  false라면 바로 종료
                break;
          }
          movecount++;  true이면 그대로 쭉 이어서 이동 횟수 카운트
    }
    

 :  System.out.println(movecount);  최종 카운트 출력
   
    
 :  static boolean bfs(int x, int y){  좌표 입력
        Queue<int[]> q = new LinkedList<>();  큐선언
        q.add(new int[]{x,y});  큐에 추가
        visit[x][y]=true;  방문처리 
        int sum = arr[x][y];  누적합 계산
        int count = 1;  이동 가능한 나라 개수 카운트
        
        List<int[]> node = new ArrayList<>();  이동 가능한 나라 좌표 저장
        node.add(new int[]{x,y});  현재 좌표 list에 추가
       
        while(!q.isEmpty()){
            int p[] = q.poll();
            for(int i=0; i<4;i++){  상하좌우로 이동
                int nx = p[0] + dx[i], ny = p[1] + dy[i];  상하좌우로 이동한 좌표
                if(0<=nx&&nx<N && 0<=ny&&ny<N && !visit[nx][ny]){  방문전이라면
                    int diff = Math.abs(arr[p[0]][p[1]]-arr[nx][ny]);  거리 차이계산
                    if(L<=diff&&diff<=R){  거리 차이가 범위 안에 있다면
                        visit[nx][ny]=true;  방문처리
                        q.add(new int[]{nx,ny});  큐에추가
                        sum += arr[nx][ny];  인구 누적합 계산
                        count++;  나라 개수 계산
                        node.add(new int[]{nx,ny});  나라 좌표 저장
                    }
                }
            }
        }
        
        if(count>1){  count가 1 이상이라는 것은 최소 한나라 이상 인구이동이 가능하다
            int avg = sum/count;  누적합/나라개수
            for(int[] n: node){  저장된 좌표 꺼내서 모두 평균으로 바꿔주기
                arr[n[0]][n[1]] = avg;
            }
            return true;  true로 출력
        }
        return false;  count가 1보다 크지 않다면 인구이동 불가하므로 false 출력
    }
  


 

 

이제 풀어보러 갈께요 :)

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *

 

 

https://www.acmicpc.net/problem/16234