백준 16234 인구이동

오답노트

- 우, 하가 아니라 4방향 검사해야 함

소스코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ_16234_인구이동 {
	static class Pos{
		int x, y;

		public Pos(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}

		@Override
		public String toString() {
			return "Pos [x=" + x + ", y=" + y + "]";
		}
		
	}
	static int n, l, r;
	static int map[][];
	static boolean visit[][];
	static final int dx[] = {-1, 0, 1, 0};
	static final int dy[] = {0, 1, 0, -1};
	static void init() {
		map = new int[n][n];
	}
	static int bfs(int sx, int sy) {
		Queue<Pos> q = new LinkedList<Pos>();
		ArrayList<Pos> list = new ArrayList<Pos>();
		q.offer(new Pos(sx, sy));
		list.add(new Pos(sx, sy));
		visit[sx][sy] = true;
		int sum = 0;
		int cnt = 0;
		while(!q.isEmpty()) {
			Pos now = q.poll();
			int x = now.x; int y = now.y;
			cnt++;
			sum += map[x][y];
			for(int i=0; i<4; i++) {
				int nx = x+dx[i]; int ny = y+dy[i];
				if(nx<0 || nx>n-1 || ny<0 || ny>n-1) continue;
				if(visit[nx][ny]) continue;
				int gap = Math.abs(map[x][y]-map[nx][ny]);
				if(l<=gap && gap<=r) {
					visit[nx][ny] = true;
					q.offer(new Pos(nx, ny));
					list.add(new Pos(nx, ny));
				}
			}
		}
		for(int i=0; i<list.size(); i++) {
			int x = list.get(i).x; int y = list.get(i).y;
			map[x][y] = sum/cnt;
		}
		
		if(cnt>1) {
			return 1;
		}
		else return 0;
		
	}
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		l = Integer.parseInt(st.nextToken());
		r = Integer.parseInt(st.nextToken());
		init();
		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 ans = 0;
		while(true) {
			visit = new boolean[n][n];
			int tmp = 0;
			for(int i=0; i<n; i++) {
				for(int j=0; j<n; j++) {
					if(!visit[i][j]) {
						tmp += bfs(i, j);
					}
				}
			}
			if(tmp>0) {
				ans++;
			}
			else {
				break;
			}
			
		}
		System.out.println(ans);
	}

}

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ_16234_인구이동 {
	static class Pos{
		int x, y;

		public Pos(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}

		@Override
		public String toString() {
			return "Pos [x=" + x + ", y=" + y + "]";
		}
		
	}
	static int n, l, r;
	static int map[][];
	static boolean visit[][];
	static final int dx[] = {-1, 0, 1, 0};
	static final int dy[] = {0, 1, 0, -1};
	static void init() {
		map = new int[n][n];
	}
	static int bfs(int sx, int sy) {
		Queue<Pos> q = new LinkedList<Pos>();
		ArrayList<Pos> list = new ArrayList<Pos>();
		q.offer(new Pos(sx, sy));
		list.add(new Pos(sx, sy));
		visit[sx][sy] = true;
		int sum = 0;
		int cnt = 0;
		while(!q.isEmpty()) {
			Pos now = q.poll();
			int x = now.x; int y = now.y;
			cnt++;
			sum += map[x][y];
			for(int i=0; i<4; i++) {
				int nx = x+dx[i]; int ny = y+dy[i];
				if(nx<0 || nx>n-1 || ny<0 || ny>n-1) continue;
				if(visit[nx][ny]) continue;
				int gap = Math.abs(map[x][y]-map[nx][ny]);
				if(l<=gap && gap<=r) {
					visit[nx][ny] = true;
					q.offer(new Pos(nx, ny));
					list.add(new Pos(nx, ny));
				}
			}
		}
		for(int i=0; i<list.size(); i++) {
			int x = list.get(i).x; int y = list.get(i).y;
			map[x][y] = sum/cnt;
		}
		
		if(cnt>1) {
			return 1;
		}
		else return 0;
		
	}
	public static void main(String[] args) throws Exception{
		System.setIn(new FileInputStream("/Users/eugene/SSAFY/work_java/CodingTest/res/인구이동.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		l = Integer.parseInt(st.nextToken());
		r = Integer.parseInt(st.nextToken());
		init();
		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 ans = 0;
		while(true) {
			visit = new boolean[n][n];
			int tmp = 0;
			for(int i=0; i<n; i++) {
				for(int j=0; j<n; j++) {
					if(!visit[i][j]) {
						tmp += bfs(i, j);
					}
				}
			}
			if(tmp>0) {
				ans++;
			}
			else {
				break;
			}
			
		}
		System.out.println(ans);
	}

}