채우다

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

• 풀이방법[알고리즘]

BFS를 활용한 구현 문제! 인구가 변경되지 않을 때까지 while문에 넣고 인구 이동을 계속 한다. 문제가 바로 눈에 들어오진 않아서 주어진 테스트 케이스들을 각각 돌려보면서 수정해나갔다. 

몇번 이동이 발생하는지 확인하기 위해 cnt값을 설정하고, 큐에 넣어서 사방탐색으로 인구이동이 가능한지 확인했다. 인구이동이 가능한 경우 hashset에 넣고, 해당 값들은 bfs가 끝난 후 계산해주었다. 인구 이동한 평균 값은 updatemap에 따로 적어뒀다가 cnt가 바뀌기 전에 업데이트해주었다.

HashSet은 스스로 중복처리를 하기 때문에 사용했는데, 직접 구현한 Point 클래스의 hashcode값이 생성할 때마다 달라져서 중복처리가 되지 않았다. 이를 해결하기 위해 hashcode와 equals 메서드를 오버라이드 하고 수정하였다.

update값을 초기화해주는 부분을 찾는것이 헷갈렸다. 해당 cnt에서 값이 수정되었는지를 확인하는 용도로 update를 설정했는데, static변수라 다른 set으로 이동해도 이어서 값을 더해서 자꾸 이상한 값이 나왔다..

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

public class Main {
//BJ16234_인구이동
	static boolean visited[][];
	static int map[][], update[][];
	static int[][] move = { { 1, 0 }, { -1, 0 }, { 0, -1 }, { 0, 1 } };
	static int N, R, L, updated;
	static boolean flag;

	public static void main(String[] args) throws Exception {
		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());

		visited = new boolean[N][N];
		map = new int[N][N];
		update = new int[N][N];
		flag = true;
		updated = 0;
		int answer = 0;

		for (int i = 0; i < map.length; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < map.length; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			} // for_2
		} // for_1

		// update가 다 0이면 더 이상의 이동이 없다
		while (flag) {
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (!visited[i][j]) {
						bfs(i, j);
					}
				}
			}
		//
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (update[i][j] != 0) {
						map[i][j] = update[i][j];
					}
				}
			}
			if (updated != 0) {
				answer++;
				updated = 0;
				
				for (int i = 0; i < visited.length; i++) {
					Arrays.fill(visited[i], false);	
					Arrays.fill(update[i], 0);
				}			
			} else {
				flag = false;
			}
		}
		System.out.println(answer);
	}// main

	static void bfs(int i, int j) {
		Queue<Point> q = new ArrayDeque<>();
		Set<Point> s = new HashSet();
		
        //q와 s에 현재 위치 넣기
		q.add(new Point(i, j));
		s.add(new Point(i, j));
		int plus =0;
		while (!q.isEmpty()) {
			Point tmp = q.poll();
			int r = tmp.r;
			int c = tmp.c;
			
			// move 배열로 사방탐색
			for (int k = 0; k < 4; k++) {
				int nr = tmp.r + move[k][0];
				int nc = tmp.c + move[k][1];
				if (nr < 0 || nr >= N || nc < 0 || nc >= N || visited[nr][nc] || Math.abs(map[nr][nc] - map[r][c]) > R
						|| Math.abs(map[nr][nc] - map[r][c]) < L)
					continue;
				// 같은 구획으로 인정 queue에 넣기
				visited[nr][nc] = true;
				q.add(new Point(nr, nc));
				// set에 point넣기
				s.add(new Point(nr, nc));
			} // FOR
		} // while
			// 지금 i,j에서 그룹확인. 연합 인구 처리 -> set에 들어간 애들은 이미 visited가 true이기 때문에 더 안본다?
		//처음 위치에서 무조건 s에 값을 넣기 때문에 1개는 들어있음
        if (s.size() > 1) {
			Iterator iter = s.iterator();
			while (iter.hasNext()) {
				Point p = (Point) iter.next();
				//System.out.println(p);
				plus += map[p.r][p.c];
			}
            
			int div = plus / s.size();
			
			iter = s.iterator();
			while (iter.hasNext()) {
				Point p = (Point) iter.next();
				update[p.r][p.c] = div;
			}
            //인구가 이동했는지 확인하는 변수
			updated=plus;
		}
	}// bfs

	static class Point {
		int r, c;
		
		@Override
		public String toString() {
			return "Point [r=" + r + ", c=" + c + "]";
		}

		@Override
		public int hashCode() {
			return this.r+this.c;
		}
		
		@Override		
		public boolean equals(Object obj) {
			if(obj instanceof Point) {
				Point tmp = (Point)obj;
				if(this.r==tmp.r && this.c==tmp.c) {
					return true;
				}
			}
			return false;
		}
		
		public Point(int r, int c) {
			this.r = r;
			this.c = c;
		}
	}// Point_Class
}// class