문제 링크
https://www.acmicpc.net/problem/16234
문제 설명
NxN 크기의 땅이 있고, 땅은 1x1 개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1x1 크기이기 때문에, 모든 국경선은 정사각형 형태이다.
오늘부터 인구 이동이 시작되는 날이다.
인구 이동은 하루 동안 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다.
- 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루 동안 연다.
- 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다.
- 국경선이 열려있어 인접한 칸만을 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다.
- 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버린다.
- 연합을 해체하고, 모든 국경선을 닫는다.
각 나라의 인구수가 주어졌을 때, 인구 이동이 며칠 동안 발생하는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N, L, R이 주어진다. (1 ≤ N ≤ 50, 1 ≤ L ≤ R ≤ 100)
둘째 줄부터 N개의 줄에 각 나라의 인구수가 주어진다. r행 c열에 주어지는 정수는 A[r][c]의 값이다. (0 ≤ A[r][c] ≤ 100)
인구 이동이 발생하는 일수가 2,000번 보다 작거나 같은 입력만 주어진다.
문제 풀이
[고려사항]
배열 크기는 최대가 50x50 이고, 인구 이동이 발생하는 일수는 최대 2,000번이다.
모든 배열을 매번 접근한다고 가정했을때, 최대 50 x 50 x 2000 = 5,000,000 (5백만)번의 접근이 있을 수 있다.
* 시간 제한 2초면 자바는 ×2+1 초라서 5초내에 완료해야한다. 그리고 초당 10^7~10^8회 연산을 수행할 수 있다고 가정했을때, 최대 접근 수가 이보다 적기 때문에 정답을 위해 크게 고려하지는 않아도 될 듯 하다. 물론 아예 생각안해도 된다는건 아니지만.
[알고리즘, 구현방법]
인접 국가를 방문하면서 인구 수 차이 조건에 따라 국경선 개방 여부를 결정할 수 있으므로, BFS 알고리즘을 사용해서 확인했다.
국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면 연합국이 되는데, 연합국은 하루에 여러개가 나올 수 있다.
그래서 연합국을 찾아 인구 이동하는 기준을 하루로 두고, 인접 국가를 탐색하는 방식으로 구현했다.
연합국을 찾아 인구 이동하는 함수인 movePeople을 반복해서, movePeople이 성공하는 경우, 인구 이동 일자를 +1 했다.
인구 이동의 성공 여부(availableFlag)는 movePeople 함수내에서 한번이라도 연합국이 만들어지면 true로 세팅하여 반환하였다.
인구 이동 함수(movePeople)에서는 인접 국가를 방문하면서 조건에 부합하면 연합국으로 묶어서 (연합국 인구 수 / 연합국 개수)명을 재분배하여 인구 이동을 구현했다. (BFS 알고리즘 사용)
상세 사항은 정답 코드의 주석을 따라가면 된다.
정답 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int[][] earth;
static int n, l, r;
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());
// 인구수 입력
earth = new int[n][n];
for (int i=0; i<n; i++) {
st = new StringTokenizer(br.readLine(), " ");
for (int j=0; j<n; j++) {
earth[i][j] = Integer.parseInt(st.nextToken());
}
}
// 인구 이동
int day = 0;
while (true) {
if (!movePeople()) break; // 인구 이동이 실패한 경우 반복문 종료
day++; // 인구 이동 성공한 경우 일 수 증가
}
System.out.println(day);
}
public static boolean movePeople() {
int[] dx = {0,1,0,-1};
int[] dy = {1,0,-1,0};
boolean[][] visited = new boolean[n][n];
Queue<Pointer> q = new LinkedList<>();
boolean availableFlag = false;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (!visited[i][j]) { // 방문하지 않은 땅인 경우
q.offer(new Pointer(i, j)); // BFS Queue에 삽입
visited[i][j] = true;
// BFS Queue에 저장되어 아래 while문을 타면 하나의 연합국으로 계산
List<Pointer> pointers = new ArrayList<>(); // 하나의 연합국 정보를 담을 Pointer 리스트
int sum = earth[i][j]; // 연합의 인구수
int cnt = 1; // 연합을 이루고 있는 칸의 개수
while (!q.isEmpty()) {
Pointer nowPointer = q.poll();
pointers.add(nowPointer);
for (int k = 0; k < 4; k++) { // 4방향 탐색
int nx = nowPointer.x + dx[k];
int ny = nowPointer.y + dy[k];
if (nx >= 0 && nx < n && ny >= 0 && ny < n) { // 범위 체크
if (!visited[nx][ny]) { // 방문하지 않은 인접 땅인 경우
int diff = Math.abs(earth[nowPointer.x][nowPointer.y] - earth[nx][ny]); // 현재 땅과 인접땅의 인구 차이 계산
if (diff >= l && diff <= r) { // L명 이상 R명 이하인 경우 국경선 열림
visited[nx][ny] = true; // 인접 땅 방문 표시
// 연합국 처리
sum += earth[nx][ny]; // 연합국 인구 수 누적
cnt++; // 연합국 개수 증가
q.add(new Pointer(nx, ny));
pointers.add(new Pointer(nx, ny)); // 현재 연합국에 추가
}
}
}
}
}
// 인구 이동을 할 수 없는 경우, 다음 땅에서 인접국 확인
if (pointers.size() == 1) continue;
// 현 연합국 인구 이동
int people = sum / cnt; // 연합에 분배될 인구 수
for (Pointer p : pointers) {
earth[p.x][p.y] = people;
}
availableFlag = true; // 인구 이동이 한번이라도 있다면 true 반환
}
}
}
return availableFlag;
}
public static class Pointer{
int x;
int y;
public Pointer(int x, int y) {
this.x = x;
this.y = y;
}
}
}'⚒️ Coding Test' 카테고리의 다른 글
| [프로그래머스] 리코쳇 로봇 (0) | 2024.08.16 |
|---|---|
| [프로그래머스] [PCCP 기출문제] 2번 / 석유 시추 - 자바(Java) (0) | 2024.08.10 |
| [백준] 탑 - 자바(Java) (0) | 2024.08.06 |
| [백준] 1, 2, 3 더하기 4 - 자바(Java) (0) | 2024.08.01 |
| [백준] 겹치는 건 싫어 - 자바(Java) (0) | 2024.07.31 |
