백준 16234 - 인구 이동

백준 16234 - 인구 이동

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

★ 풀이

문제를 읽으면 이중포문 안에 BFS를 사용해서 모든 나라에 대해 검사를 하며 4방향 탐색을 통해 조건에 맞는 좌표끼리 그룹화를 시켜주는 것 까지는 쉽게 알 수 있다. 처음엔 따로 이차원 배열을 생성해서 해볼까라는 생각도 들었지만 그것 보다는 따로 Queue 를 생성해서(nations) 그룹별로 바로 평균점수를 분배하는것이 더 효율적이라는 생각이 들어서 그렇게 처리했다.

(+ 다시보니 마지막에 day를 처리할때 초기값을 -1로 주는게 보기에 더 좋았을 것 같다.)

★ 소스 코드

import java.io.*; import java.util.*; class Point{ int x; int y; Point(int x, int y){ this.x = x; this.y = y; } } class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); static int n,l,r; static int board[][]; static boolean changed; static boolean visited[][]; static int day; static Queue nations = new LinkedList(); public static void main(String args[]) throws Exception { // 인구 이동이 몇일 동안 발생하는지 구해야함 StringTokenizer st = new StringTokenizer(br.readLine()); n = Integer.parseInt(st.nextToken()); l = Integer.parseInt(st.nextToken()); r = Integer.parseInt(st.nextToken()); board = new int[n][n]; day = 0; for(int i = 0; i q = new LinkedList<>(); q.add(new Point(x,y)); int sum = 0; int cnt = 0; while (!q.isEmpty()) { Point p = q.poll(); if (!visited[p.x][p.y]) { visited[p.x][p.y] = true; nations.add(new Point(p.x,p.y)); sum += board[p.x][p.y]; cnt ++; for (int i = 0; i < 4; i++) { int nx = p.x + dx[i]; int ny = p.y + dy[i]; if (nx >= 0 && ny >= 0 && nx < n && ny < n) { int diff = Math.abs(board[p.x][p.y] - board[nx][ny]); if (diff <= r && diff >= l) { changed = true; q.add(new Point(nx, ny)); } } } } } return sum/cnt; } }

from http://sweet-smell.tistory.com/51 by ccl(A) rewrite - 2021-09-16 03:27:41