[백준] 16234_인구이동 (JAVA)

1. 문제

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

16234번: 인구 이동

---

 

 

2. 문제 풀이 겸 회고

음 우선 정답률 36퍼라 해서 쫄았는데 훗 한방에 품 (호오옥시나 예외처리 못했을까 봐 ㅎㅅㅎ..)

생각한 방식

위의 문구 보고 시뮬임을 느꼈다.

문제를 읽어보니 시뮬 + bfs 같았다.

bfs 확신을 느낀 부분은 국경선이 열려있어 인접한 칸만 이동할 수 있다고 했는데

 

L 이상 R 이하만 두 나라 공유 한다고 했으니깐 

만약 L = 1 , R = 3 이라고 하면

ㅋㅋ 그림판 안습..ㅠ

암튼 저렇게 나눠지니깐 이제  5부터 상하좌우(인접) 비교 (방향 탐색) 해서 R, C 조건에 맞으면 queue에 저장하고 이렇게 점점 나아가면 된다고 생각했음 ( 갈 수 있는 곳은 다가기)  

[내가 푼 방식]

1. 공유할 수 있는 나라들 구해주기  

 1 - 1. share한 나라끼리 사람 나눠가져야 하니깐,또 다른 큐 선언해서 공유한 나라 위치 저장해주기

  1 - 2. 변수 선언해서 각 나라 인구수도 계속 더해서 저장해두기

2. 한 구역( bfs)이 끝나면 

3. 더한 인구수 /  공유한 나라의 위치가 담긴 큐 사이즈 ( 나라 수)

4. 공유한 나라 위치가 담긴 큐에서 위치 빼서 해당 위치에 (3번에서 계산한) 값 넣어줌

5. 공유할 수 없을 때까지 while 돌려줌!!! (boolean 변수 flag로 bfs에서 공유할 수 있는 나라를 구할 수 있으면 true로 하는 방식으로 함)

 

끗!

- 방문 체크, 맵 경계 체크는 필수 ^^!

뼛속까지 공대생이라 중구난방의 글 이해해주시길 바라며...

 

 

 

3. 코드

package net.acmicpc.samsung;

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

public class Solution_16234_인구이동 {

	static class Point {
		int r;
		int c;

		public Point(int r, int c) {
			this.r = r;
			this.c = c;
		}
	}

	static int N, L, R;
	static boolean flag;
	static int[][] map;
	static boolean[][] v;

	static int[] dr = { 1, 0, -1, 0 };
	static int[] dc = { 0, -1, 0, 1 };

	public static void main(String[] args) throws IOException {
		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());
		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());
			}
		}
		flag = true;
		int answer = -1;

		while (flag) {
			v = new boolean[N][N];
			flag = false;

			shareCountry();
			answer++;

		}
		System.out.println(answer);
	}

	static Queue<Point> que;

	private static void shareCountry() {
		que = new LinkedList<>();
		for (int r = 0; r < N; r++) {
			for (int c = 0; c < N; c++) {
				if (!v[r][c]) {
					que.offer(new Point(r, c));
					v[r][c] = true;
					int sum = map[r][c];
					tmq = new LinkedList<>();
					tmq.offer(new Point(r, c));
					bfs(sum);
				}
			}
		}
	}

	static Queue<Point> tmq;

	private static void bfs(int sum) {
		while (!que.isEmpty()) {
			Point cur = que.poll();

			for (int d = 0; d < 4; d++) {
				int nr = cur.r + dr[d];
				int nc = cur.c + dc[d];

				if (!check(nr, nc))
					continue;
				int val = Math.abs(map[nr][nc] - map[cur.r][cur.c]);

				if (!v[nr][nc] && (val >= L && val <= R)) {
					sum += map[nr][nc];
					v[nr][nc] = true;
					que.offer(new Point(nr, nc));
					tmq.offer(new Point(nr, nc));
					flag = true;

				}
			}
		}
		
        movePeople(sum);

	}

	private static void movePeople(int sum) {
		//print();
		//System.out.println();
		int p = sum / tmq.size();
		while (!tmq.isEmpty()) {
			Point cur = tmq.poll();
			map[cur.r][cur.c] = p;
		}
	}

	private static boolean check(int nr, int nc) {
		return nr >= 0 && nr < N && nc >= 0 && nc < N;
	}

	private static void print() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				System.out.print(map[i][j] + " ");
			}
			System.out.println();
		}
	}
}

 

 

 

피드백은 언제나 환영입니다 :) 🌳