[BOJ - JAVA] 16234 - 인구 이동(BFS)

# 주소

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

16234번: 인구 이동

# 문제

# 문제 해설 및 코드 리뷰

import java.awt.*;
import java.util.*;
class Main{
    static int n,l,r;
    static int[][] arr;
    static int[] dx = {-1,0,1,0};
    static int[] dy = {0,1,0,-1};
    static boolean[][] visit;
    static int day = 0;
    static Queue<Point> queue = new LinkedList<>();
    static Queue<Point> q = new LinkedList<>();
    static ArrayList<Integer> list = new ArrayList<>();
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt(); l = scan.nextInt(); r = scan.nextInt();
        arr = new int[n][n];
        visit = new boolean[n][n];
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                arr[i][j] = scan.nextInt();
        if(check())
            bfs();
        else {
            System.out.println(0);
            System.exit(0);
        }
        System.out.println(day);
    }
    static void bfs(){
        list = new ArrayList<>();
        visit = new boolean[n][n];
        queue = new LinkedList<>();
        for(int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(visit[i][j])
                    continue;
                else {
                    queue.offer(new Point(i, j));
                    q.offer(new Point(i,j));
                    visit[i][j] = true;
                    list.add(arr[i][j]);
                    while (!queue.isEmpty()) {
                        Point now = queue.poll();
                        for (int t = 0; t < 4; t++) {
                            int nx = now.x + dx[t];
                            int ny = now.y + dy[t];
                            if (nx < 0 || ny < 0 || nx >= n || ny >= n) {
                                continue;
                            }
                            if (!visit[nx][ny]) {
                                if (Math.abs(arr[now.x][now.y] - arr[nx][ny]) >= l &&
                                        Math.abs(arr[now.x][now.y] - arr[nx][ny]) <= r) {
                                    queue.offer(new Point(nx,ny));
                                    q.offer(new Point(nx,ny));
                                    list.add(arr[nx][ny]);
                                    visit[nx][ny] = true;
                                }
                            }
                        }
                    }
                }
                if(list.size() > 0)
                    search();
                list = new ArrayList<>();
                queue = new LinkedList<>();
            }
        }
        if(check()){
            bfs();
        }
        day++;
    }
    static void search(){
        int size = list.size();
        int sum = 0;
        for(int i = 0; i < size; i++){
            sum += list.get(i);
        }
        int num = sum / size;
        while(!q.isEmpty()){
            Point now = q.poll();
            arr[now.x][now.y] = num;
        }
    }
    static boolean check(){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                for(int t = 0; t < 4; t++){
                    int nx = i + dx[t];
                    int ny = j + dy[t];
                    if(nx < 0 || ny < 0 || nx >= n || ny >= n)
                        continue;
                    if(Math.abs(arr[i][j] - arr[nx][ny]) >= l &&
                    Math.abs(arr[i][j] - arr[nx][ny]) <= r)
                        return true;
                }
            }
        }
        return false;
    }
}

한 3시간 걸렸던 문제입니다.

코드가 넘 길어서 ㅠㅠ 이거보다 더 간단하게 푸는법 아시면 댓글 부탁드립니다..

저는 bfs를 이용해서 풀었습니다.

차근차근 살펴봅시다.

static int n,l,r;
static int[][] arr;
static int[] dx = {-1,0,1,0};
static int[] dy = {0,1,0,-1};
static boolean[][] visit;
static int day = 0;
static Queue<Point> queue = new LinkedList<>();
static Queue<Point> q = new LinkedList<>();
static ArrayList<Integer> list = new ArrayList<>();

dx,dy를 상,하,좌,우로 가기 때문에 4가지 방향을 설정합니다.

벡터의 방향을 의미하는 것과 같습니다. (기저)

2차원 배열인 int타입의 arr와 boolean타입의 visit을 선언합니다.

그리고 정답이 될 day = 0으로 잡고 큐가 2개 필요하기 때문에 queue, q를 각각 선언합니다.

queue는 새로운 점을 담을 것인데 nx,ny를 담고 소멸될 자료구조이고

q는 새로운 점을 같이 담는데 그대로 끌고갈 것이며

ArrayList<>의 list는 arr[i][j]의 값을 담을 것입니다.

Scanner scan = new Scanner(System.in);
n = scan.nextInt(); l = scan.nextInt(); r = scan.nextInt();
arr = new int[n][n];
visit = new boolean[n][n];
for(int i = 0; i < n; i++)
    for(int j = 0; j < n; j++)
        arr[i][j] = scan.nextInt();
if(check())
    bfs();
else {
    System.out.println(0);
    System.exit(0);
}
System.out.println(day);

제 블로그 보시면 아시겠지만 웬만해선 입력받을 때 Scanner를 사용합니다.

가독성을 위해서이기도 하고 정답에 무리만 없으면 자주 사용합니다.

n,l,r을 입력받고 arr와 visit의 크기를 n x n으로 지정합니다.

이후 arr를 입력받습니다.

 

check()함수를 실행하여 true일 때는 bfs문을 실행할 것입니다.

check()함수는, 이 arr가 l보다 크거나 같고 r보다 작거나 같은지를 보기 위함입니다.

따라서

static boolean check(){
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            for(int t = 0; t < 4; t++){
                int nx = i + dx[t];
                int ny = j + dy[t];
                if(nx < 0 || ny < 0 || nx >= n || ny >= n)
                    continue;
                if(Math.abs(arr[i][j] - arr[nx][ny]) >= l &&
                Math.abs(arr[i][j] - arr[nx][ny]) <= r)
                    return true;
            }
        }
    }
    return false;

check()함수의 내부를 살펴보면 삼중 for문을 이용하여 nx, ny를 설정하는걸 알 수 있는데요.

만약

if(Math.abs(arr[i][j] - arr[nx][ny]) >= l &&
Math.abs(arr[i][j] - arr[nx][ny]) <= r)
    return true;

arr간의 간격이 l보다 크거나 같고 r보다 작거나 같은게 하나라도 있으면 return true를 내보내어 bfs를 실행합니다.

하지만 그렇지 않을 경우 return false를 내보내어 0을 출력하고 main함수를 종료합니다.

bfs문 내부 구조를 살펴보겠습니다.

for(int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        if(visit[i][j])
            continue;

만약 visit이 true인 경우엔 탐색할 필요가 없으므로 continue합니다.

즉, 값이 담길 수 있는 것만 queue에 담고 visit도 true로 바꾸어줄 것입니다.

else {
    queue.offer(new Point(i, j));
    q.offer(new Point(i,j));
    visit[i][j] = true;
    list.add(arr[i][j]);

따라서 visit이 false인 (i,j)만 탐색할 것인데, 이 때 queue와 q에 각각의 (i,j)를 담고 visit = true, list에는 arr[i][j]를 담습니다.

while (!queue.isEmpty()) {
    Point now = queue.poll();
    for (int t = 0; t < 4; t++) {
        int nx = now.x + dx[t];
        int ny = now.y + dy[t];
        if (nx < 0 || ny < 0 || nx >= n || ny >= n) {
            continue;
        }

이후 Point now = queue.poll()하여 인덱스를 갖고와서 각각의 nx, ny를 4방향에 따라 설정합니다.

이 nx,ny가 0보다 작거나 n보다 크거나 같으면 continue하는 것이 핵심입니다.

그리고

if (!visit[nx][ny]) {
    if (Math.abs(arr[now.x][now.y] - arr[nx][ny]) >= l &&
            Math.abs(arr[now.x][now.y] - arr[nx][ny]) <= r) {
        queue.offer(new Point(nx,ny));
        q.offer(new Point(nx,ny));
        list.add(arr[nx][ny]);
        visit[nx][ny] = true;
    }
}

이 문제에서 가장 중요한 로직입니다.

visit = false인 곳에 대하여 각각의 인접한 값들의 차이가 l보다 크거나 같고 r보다 작거나 같은 값들에 대해서 queue, q에 담고 list에는 arr[nx][ny]를 담으며 visit도 true로 바꾸어 줍니다.

탐색이 모두 끝났으면 while문을 빠져나와 search()문을 실행합니다.

static void search(){
    int size = list.size();
    int sum = 0;
    for(int i = 0; i < size; i++){
        sum += list.get(i);
    }
    int num = sum / size;
    while(!q.isEmpty()){
        Point now = q.poll();
        arr[now.x][now.y] = num;
    }
}

search문은 다음과 같습니다.

sum = 0, size = list.size()로 갖고온 뒤 sum에는 list의 모든 값들을 더합니다.

이후 size로 나누어 준 값을 num에 저장하고 갖고온 q에 대하여 arr의 값들을 모두 num으로 바꿉니다.

이것이 q를 사용하는 이유입니다.

queue만 홀로 사용하게 되면 여기 있는 이 인덱스들을 방금의 while문 때문에 밖으로 가져올 방법이 없습니다.

peek()를 써볼까도 싶었지만 잘 안되어서 q를 새로 선언하여 갖고왔는데, 혹시 다른 방법 아시면 알려주세요.

다시 본론으로 들어가서 search문을 빠져나오면

if(list.size() > 0)
    search();
list = new ArrayList<>();
queue = new LinkedList<>();

list와 queue는 모두 초기화합니다.

이후

if(check()){
    bfs();
}
day++;

check()를 재실행하여, 만약 true면 다음날에도 다시 연합을 해야하므로 bfs문을 실행하고

그렇지 않다면 day++하여 bfs문을 그대로 종료합니다.

최종적으로 day를 출력하면 그것이 정답이 됩니다.

 

골드5문제인데, 꽤 어려운 것 같습니다.

실제로 정답률이 35%이기도 하고 로직도 굉장히 긴데 (제가 길게 쓴건지,..) 어쨌든 풀었으니 다행입니다.

감사합니다.