[백준 / JAVA] 16234. 인구 이동 (G4)

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

아니 이거 네모 미리보기 왜 안 나와?

 

내가 풀었지만 푼 것 같은 기분이 안든다...BFS 할 때 저장용 큐에 처음 방문한 큐를 넣어도 되나 라는 고민이 있었다. 이걸 넣자니 주변에 조건을 만족하는 칸이 없을 때 값일 달라질까봐 그랬다. 그런데 연결된 부분을 더하고 나누는 과정에서 저장용 큐의 크기가 1이면 하나의 칸의 값을 1로 나누는 거라 결과적으로 값이 유지된 채 큐만 비워진다! 그래서 아름답게 풀린다. 근데 이걸 내가 노린 게 아니라서 찝찝하다...

 

6시간 동안 고민한건 아니다.

 

import java.io.*;
import java.util.*;

public class Main {
	static BufferedReader br;
	static StringTokenizer st;
	static StringBuilder sb;

	public static void main(String[] args) throws Exception {
		br = new BufferedReader(new InputStreamReader(System.in));
		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 answer = 0;
		while (move()) {
			answer++;
		}
		System.out.println(answer);
	}

	static int N, L, R, map[][], dr[] = { -1, 1, 0, 0 }, dc[] = { 0, 0, -1, 1 };

	static boolean move() {
		boolean flag = false;
		boolean visited[][] = new boolean[N][N];
		Deque<Point> q = new ArrayDeque<>();
		Deque<Point> memoryQ = new ArrayDeque<>();
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (!visited[i][j]) { // 이 내부에서 dfs
					visited[i][j] = true;
					q.add(new Point(i, j));
					memoryQ.add(new Point(i, j));
					while (!q.isEmpty()) {
						Point cur = q.poll();
						for (int d = 0; d < 4; d++) {
							int nr = cur.row + dr[d];
							int nc = cur.col + dc[d];
							if (nr < 0 || nr >= N || nc < 0 || nc >= N || visited[nr][nc])
								continue;
							int gap = Math.abs(map[cur.row][cur.col] - map[nr][nc]);
							if (gap >= L && gap <= R) {
								q.add(new Point(nr, nc));
								visited[nr][nc] = true;
								memoryQ.add(new Point(nr, nc));
								flag = true;
							}
						}
					}
				}
				if (!memoryQ.isEmpty()) {
					int sum = 0;
					for (Point p : memoryQ)
						sum += map[p.row][p.col];
					int people = sum / memoryQ.size();
					while (!memoryQ.isEmpty()) {
						Point cur = memoryQ.poll();
						map[cur.row][cur.col] = people;
					}
				}
			}
		}
		return flag;
	}

	static class Point {
		int row, col;

		public Point(int row, int col) {
			super();
			this.row = row;
			this.col = col;
		}
	}
}