문제
풀이
구현 + 완전탐색 문제이다. 완전탐색은 BFS로 구현하였다. BFS는 평균적인 성능(시간)이 DFS보다 좋다.
현재 위치에서 상하좌우를 탐색하면서 |현재 칸 인구 수 - 탐색 칸 인구 수| 가 주어진 범위 내에 있으면 해당 위치를 큐에 넣고 현재 연합의 정보를 저장한 리스트에 넣는다.
큐가 빌 때까지 탐색하고, 탐색이 끝나면 현재 연합의 인구수를 조정한다.
중요한 부분
하루 인구이동 할 때마다 인구이동이 일어났는지 확인하는 check 배열 초기화가 일어난다.
만약, 하루동안 위와 같이 연합이 두개 생긴다면, 노란색 탐색이 끝난 후, 빨간색도 탐색해야 한다.
따라서, 하루동안은 같은 boolean[] check 배열을 사용해야 한다.
// 인구 이동 더 이상 일어나지 않을 때까지
while(true){
boolean areTheyUnited = false;
boolean[][] check = new boolean[size][size];
//
for(int i = 0; i < size; i++){
for(int j = 0; j < size; j++){
if(check[i][j] == false){
queue.add(new Pos(j, i));
if(BFS(queue, check, arr, L, R)) {
areTheyUnited = true;
}
}
}
}
if(areTheyUnited){
day++;
}
else break;
}check[i][j] 가 false일 때 BFS 탐색을 시작한다.
진짜 중요한 부분 (BFS에서 메모리 초과 관련)
아래는 현 위치에서 갈 수 있는 위치를 너비우선 탐색하고, 인구 이동을 시키는 함수이다.
public static boolean BFS(Queue<Pos> queue, boolean[][] check, int[][] arr, int L, int R){ int sum = 0; List<Pos> currUnion = new ArrayList<>(); // while(!queue.isEmpty()){ Pos currPos = queue.poll(); int currX = currPos.x; int currY = currPos.y; // for(int i = 0; i < 4; i++){ //북남동서 확인 int nextX = currX + dirX[i]; int nextY = currY + dirY[i]; if((nextX >= 0 && nextX < arr.length) && (nextY >= 0 && nextY < arr.length)){ //범위 내 확인 if(!check[nextY][nextX]){ //아직 방문하지 않았으면 int div = Math.abs(arr[currY][currX] - arr[nextY][nextX]); //인구차이 if(div >= L && div <= R){ queue.add(new Pos(nextX, nextY)); //방문 check[nextY][nextX] = true; sum += arr[nextY][nextX]; currUnion.add(new Pos(nextX, nextY)); } } } } } // 인구 이동이 일어났으면 if(currUnion.size() >= 2){ int unitedNum = sum / currUnion.size(); // 인구 이동 후 인구 수 for(Pos pos : currUnion){ arr[pos.y][pos.x] = unitedNum; } return true; } else return false; }만약
check[nextY][nextX] = true;
위 그림에서, (check[y][x])
1. (0,0)에서 탐색한 (1,0), (0,1)이 큐에 들어간다. check[0][0] = true;
2. 큐에서 (1,0)을 꺼내고 (2,0), (1,1)이 큐에 들어간다. check[0][1] = true;
3. 큐에서 (0,1)을 꺼내고 (1,1)이 큐에 들어간다. check[1][0] = true;
--> 문제 발생. (1,1)이 중복으로 큐에 들어간다. 즉, 중복으로 탐색하는 것이다.
따라서, check[y][x] = true; 코드를 현재 위치에서 갈 수 있는 위치를 탐색하는 부분에 써줌으로써 해결했다.
BFS를 구현 할 때, 중복방문 하는 일이 없도록 잘 생각해서 코드를 짜야 한다.
전체 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
// L <= 인구 차이 <= R 이면 인구 이동 (총 인구수 / 연합 수)
// 위 매커니즘 반복 -> 총 며칠 인구이동 일어나는지
// BFS로 인구이동 일어날 수 있는 칸들 탐색한 후, 인구이동 시키기
public class Boj16234 {
//public class Main {
public static int[] dirX = {0, 1, 0, -1}; //북동남서
public static int[] dirY = {-1, 0, 1, 0};
public static class Pos{
int x;
int y;
public Pos(int x, int y){
this.x = x;
this.y = y;
}
}
public static boolean BFS(Queue<Pos> queue, boolean[][] check, int[][] arr, int L, int R){
int sum = 0;
List<Pos> currUnion = new ArrayList<>();
while(!queue.isEmpty()){
Pos currPos = queue.poll();
int currX = currPos.x;
int currY = currPos.y;
for(int i = 0; i < 4; i++){ //북남동서 확인
int nextX = currX + dirX[i];
int nextY = currY + dirY[i];
if((nextX >= 0 && nextX < arr.length) && (nextY >= 0 && nextY < arr.length)){ //범위 내 확인
if(!check[nextY][nextX]){ //아직 방문하지 않았으면
int div = Math.abs(arr[currY][currX] - arr[nextY][nextX]); //인구차이
if(div >= L && div <= R){
queue.add(new Pos(nextX, nextY)); //방문
check[nextY][nextX] = true; // 다음에 갈 곳들은 무조건 갈 곳임. 근데 이 코드를 여기에 안쓰고 위에서 쓰면 중복으로 방문하게 됨.
sum += arr[nextY][nextX];
currUnion.add(new Pos(nextX, nextY));
}
}
}
}
}
// 인구 이동이 일어났으면
if(currUnion.size() >= 2){
int unitedNum = sum / currUnion.size(); // 인구 이동 후 인구 수
for(Pos pos : currUnion){
arr[pos.y][pos.x] = unitedNum;
}
return true;
}
else return false;
}
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
int size = Integer.parseInt(stringTokenizer.nextToken()); //한 변의 길이
int L = Integer.parseInt(stringTokenizer.nextToken());
int R = Integer.parseInt(stringTokenizer.nextToken());
int[][] arr = new int[size][size];
for(int i = 0; i < size; i++){
stringTokenizer = new StringTokenizer(bufferedReader.readLine());
for(int j = 0; j < size; j++){
arr[i][j] = Integer.parseInt(stringTokenizer.nextToken());
}
}
int day = 0;
Queue<Pos> queue = new LinkedList<>();
// 인구 이동 더 이상 일어나지 않을 때까지
while(true){
boolean areTheyUnited = false;
boolean[][] check = new boolean[size][size];
for(int i = 0; i < size; i++){
for(int j = 0; j < size; j++){
if(check[i][j] == false){
queue.add(new Pos(j, i));
if(BFS(queue, check, arr, L, R)) {
areTheyUnited = true;
}
}
}
}
if(areTheyUnited){
day++;
}
else break;
}
System.out.println(day);
}
}
Record What I Learned