[Java Algorithm] 인구 이동 BOJ #16234

문제

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

16234번: 인구 이동

 

내 문제 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {
	
	static int n, l, r;
	static int[][] map, visited;
	static int cnt, sum; // 현재 연합의 나라 개수, 현재 연합의 총 인구수
	static int teams, day; // 하루에 해당하는 연합의 개수, 날짜 카운트
	static int[] dx = {0, 0, -1, 1};
	static int[] dy = {-1, 1, 0, 0};
	static Deque<int[]> que = new ArrayDeque<>();
	
	public static void bfs(int i, int j) { // 연합 찾기 (연합을 이루는 나라는 visited에 1로 표시)
		while(!que.isEmpty()) {
			int[] now = que.removeFirst();
			int x = now[0];
			int y = now[1];
			
			for(int a = 0; a < 4; a++) {
				int nx = x + dx[a];
				int ny = y + dy[a];
				
				if(nx < 0 || ny < 0 || nx >= n || ny >= n || visited[nx][ny] != 0) continue; // 범위를 벗어나거나 이미 방문한적 있는 곳일 떼
				if(Math.abs(map[x][y] - map[nx][ny]) < l || Math.abs(map[x][y] - map[nx][ny]) > r) continue; // 인구 차가 기준에 벗어날 때
				
				visited[nx][ny] = 1;
				sum += map[nx][ny];
				cnt++;
				que.add(new int[]{nx, ny});
			}
		}
		
		visited[i][j] = -1; // 시작점 방문 체크만 남겨놓기
		if(cnt > 1) { // 연합이 이루어졌을 떄
			teams++; // 연합 하나 발견했음을 표시
			map[i][j] = sum /cnt; // 시작점만 먼저 인구 이동 시켜주기
			que.add(new int[]{i, j});
			update(map[i][j]);
		}
	}
	
	public static void update(int popul) { // 인구 이동시켜주면서, 인구 이동을 마친 나라의 visited는 -1로 바꿔주기
		while(!que.isEmpty()) {
			int[] now = que.removeFirst();
			int x = now[0];
			int y = now[1];
			
			for(int a = 0; a < 4; a++) {
				int nx = x + dx[a];
				int ny = y + dy[a];
				
				if(nx < 0 || ny < 0 || nx >= n || ny >= n || visited[nx][ny] != 1) continue; // 범위를 벗어나거나 현재 찾는 연합이 아닐 때
				
				map[nx][ny] = popul; // 인구이동
				visited[nx][ny] = -1; // 인구이동을 마친 연합임을 표시
				que.add(new int[]{nx, ny});
			}
		}
	}

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		st = new StringTokenizer(in.readLine());
		n = Integer.parseInt(st.nextToken());
		l = Integer.parseInt(st.nextToken());
		r = Integer.parseInt(st.nextToken());
		map = new int[n][n];
		visited = new int[n][n];
		day = 0;
		
		for(int i = 0; i < n; i++) {
			st = new StringTokenizer(in.readLine());
			for(int j = 0; j < n; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		while(true) { // 한 번의 while 반복 == 하루
			teams = 0;
			for(int i = 0; i < n; i++) {
				for(int j = 0; j < n; j++) {
					if(visited[i][j] == 0) {
						que.add(new int[]{i, j});
						cnt = 1;
						sum = map[i][j];
						visited[i][j] = 1;
						bfs(i, j);
					}
				}
			}
			if(teams == 0) { // 연합이 하나도 없을 때
				System.out.println(day);
				return;
			}
			for(int i = 0; i < n; i++) {
				for(int j = 0; j < n; j++) {
					visited[i][j] = 0;
				}
			}
			
			day++;
		}
	}
}

👉 BFS 문제

• visited를 차례대로 탐색하면서 연합을 이루지 않은 나라를 찾아주었다.
  visited는 int형 2차원 배열인데, 0 혹은 1 혹은 -1만 저장될 수 있게 했다.
  (0: 연합을 이루지 않은 나라 / -1: 이미 체크해준 나라 / 1: 현재 연합을 이루는 나라)
• 2중 for문을 돌면서 visited가 0인 나라를 만나면, 아직 연합을 구하지 못한 나라이므로
  bfs 함수를 통해 연합이 될 수 있는지 주변을 체크해주었다.
• bfs에서는 상하좌우를 탐색하며 연합이 될 수 있는지 확인 후,
  될 수 있는 나라 발견 시 연합이 되었음을 표시하기 위해 visited를 1로 바꿔주었다. 
  그리고 그와 동시에 sum에 해당 나라의 인구 수를 더하고,
  cnt 변수를 1 늘려서 연합 나라의 개수를 세어주었다.
• 위와 같은 탐색을 반복하다가 더 이상 연합이 될 수 있는 나라가 없다면
  update 함수를 불러서 인구 이동과 visited 함수 업데이트를 시켜주었다.
• update 함수는 sum / cnt를 파라미터로 받고,
  bfs 함수와 마찬가지로 que를 이용해 bfs 탐색을 할 수 있도록 작성했다.
  (어차피 방금 탐색했던 연합은 모두 인접해있으므로 bfs를 이용해 효율적으로 탐색 가능)
• update에서는 탐색을 하면서 연합에 해당하는 나라들의 인구를 업데이트 시켰고,
  인구 이동을 완료한 나라는 visited를 -1로 바꿔주어 이미 체크가 완료된 나라임을 표시했다.
• 위와 같은 실행을 map의 모든 나라를 체크할 때까지 반복하고,
  반복이 끝나면 teams 변수를 확인하여 연합이 하나라도 있었는지를 체크했다.
  teams 변수는 bfs 함수에서 하나의 연합을 발견하면 ++해주었는데,
  teams변수가 0이라면 한 개의 연합도 없었다는 의미이므로 결과를 출력하고 return 했다.
• teams 변수가 0이 아니면 연합이 하나 이상 있었다는 의미이며,
  이는 다음 날의 인구 이동도 있을 수 있다는 가능성을 내포하므로 다음 반복을 또 다시 진행시켰다.

 

 

💡 피드백

• 두 가지 종류의 bfs 함수를 작성하면 쉽게 풀 수 있는 문제였다.