백준 16234 인구이동 - 삼성 SW 역량 테스트 기출

백준 16234 인구이동 - 삼성 SW 역량 테스트 기출

1. 문제 링크

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

16234번: 인구 이동

 

2. 문제 해결에 대한 아이디어

1. 모든 좌표에 대해 연합 조사를 진행하며, 이미 연합이 있는 경우는 제외한다.

2. 연합에 대한 numbering을 하기 위해 int[][] visit에 연합 번호를 넣었다.

3. 연합 번호는 매 BFS가 끝난 뒤 1 증가한다.

4. BFS에서 연합이 되는 모든 위치를 ArrayList<Pair> union에 저장한다.

5. BFS가 완료되면 (연합 번호, union)을 hm(해쉬맵)에 저장한다.

6. 모든 좌표에 대한 BFS가 완료되면 hm에 있는 정보를 가져와 인구 분배를 한다.

 

3. 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

public class Main {

	static class Pair {
		int y, x;

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

	}

	static int[] dirY = { 0, 0, 1, -1 };
	static int[] dirX = { 1, -1, 0, 0 };
	static int[][] board;
	static int[][] visit;
	static int unionNo = 1;
	static int day = 0;
	static int N, L, R;
	static HashMap<Integer, ArrayList<Pair>> hm;

	public static void main(String[] args) throws Exception {
//		BufferedReader br = new BufferedReader(new FileReader(
//				"C:\\Users\\admin\\git\\java-algorithm\\src\\main\\java\\boj\\삼성기출\\인구이동_16234\\input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String[] nlr = br.readLine().split(" ");
		N = Integer.parseInt(nlr[0]);
		L = Integer.parseInt(nlr[1]);
		R = Integer.parseInt(nlr[2]);

		board = new int[N][N];
		hm = new HashMap<>();
		for (int i = 0; i < N; i++) {
			String[] line = br.readLine().split(" ");
			for (int j = 0; j < N; j++) {
				board[i][j] = Integer.parseInt(line[j]);

			}
		}

		while (true) {
			visit = new int[N][N];
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (visit[i][j] == 0) {
						makeUnion(i, j);
					}
				}
			}

			if (hm.isEmpty())
				break;

			divideEnd();
			++day;
		}

		System.out.println(day);

	}

	static void makeUnion(int i, int j) {
		ArrayList<Pair> union = new ArrayList<>();
		Pair p = new Pair(i, j);
		Queue<Pair> q = new LinkedList<>();
		q.add(p);
		visit[p.y][p.x] = unionNo;
		while (!q.isEmpty()) {
			Pair now = q.poll();
			int y = now.y;
			int x = now.x;
			union.add(new Pair(y, x));
			for (int d = 0; d < 4; d++) {
				int yy = now.y + dirY[d];
				int xx = now.x + dirX[d];

				if (yy < 0 || xx < 0 || yy >= N || xx >= N || visit[yy][xx] != 0)
					continue;

				int gap = Math.abs(board[y][x] - board[yy][xx]);
				if (gap < L || gap > R)
					continue;

				visit[yy][xx] = unionNo;
				q.add(new Pair(yy, xx));
			}
		}

		if (union.size() == 1) {
			return;
		}

		hm.put(unionNo, union);
		++unionNo;
	}

	static void divideEnd() {
		for (Integer key : hm.keySet()) {
			ArrayList<Pair> union = hm.get(key);
			int total = 0;
			for (int i = 0; i < union.size(); i++) {
				Pair p = union.get(i);
				total += board[p.y][p.x];
			}
			int newNum = total / union.size();
			for (int i = 0; i < union.size(); i++) {
				Pair p = union.get(i);
				board[p.y][p.x] = newNum;
			}
		}

		hm.clear();
		unionNo = 1;
	}

}

 

4. 채점 결과

 

5. 느낀 점

1. HashMap에 저장하지 않고 바로 union에 있는 정보를 가지고 인구 분배를 했어도 가능하다.

2. 특별히 신경써야하는 디테일이 없었기 때문에 쉬운 편이었다.