[동계 모각코 3주차] BFS 알고리즘 풀이

BFS 알고리즘

너비우선탐색으로 가까운 곳부터 탐색하는 알고리즘이다. 이를 위해 FIFO 방식인 Queue 자료구조를 사용하여 방문할 순서를 정한다.
이와 대비하여 DFS알고리즘도 존재하는데 이는 재귀함수 또는 Stack 자료구조를 사용하여 방문할 순서를 정하는 알고리즘이다.

 

이 문제는 L과 R을 입력 받고 각 나라 즉 각 배열 한 칸이 인접한 나라와 비교했을 때 L이상 R이하라면 인구 이동이 일어나는 상황이다. 이를 지속해서 이동하다가 인구 이동이 더 이상 일어나지 않을 때를 구하는 문제이다. 이를 보고 그래프 문제라고 생각을 했고 인접한 것을 계속해서 구해야하기에 BFS알고리즘을 사용해 문제풀이를 해나갔다. 문제를 풀다보니 반복문을 겹쳐서 많이 사용했는데, 입력의 크기가 작아서 그 부분은 깊이 생각하지 않고 문제풀이를 진행하였다.

 

1. 인구이동이 일어나지 않을 때까지 구해야하기 때문에 가장 크게 while 반복문을 사용하고 changed 변수로 멈춰줄 수 있게 함.

2. 각 배열의 칸마다 모두 조사하여야 하기 때문에 이중 반복문으로 각 요소들을 탐색해줌.

3. 인접한 나라들의 이동 유무를 파악하기 위해 BFS알고리즘을 사용하여 각 인접 나라들의 이동 가능 여부를 파악해줌.

4. 그렇게 국경선을 공유하는 나라들의 인구수를 반영해줌. (이 때 visited배열이 존재하기에 탐색하지 않은 다른 요소에 영향을 주지 않음.)

5.  처음 만들어준 while문 마지막부분에 changed의 변화, days를 반영해주며 코드를 마무리하였다.

 

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

public class b_16234 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int L = Integer.parseInt(st.nextToken());
        int R = Integer.parseInt(st.nextToken());
        int diff = R - L;
        int[][] arr = new int[N][N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        int[] dy = {1, -1, 0, 0};
        int[] dx = {0, 0, 1, -1};
        int days = 0;
        while (true) {
            boolean[][] visited = new boolean[N][N];
            boolean changed = false;

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (!visited[i][j]) {
                        ArrayList<int[]> list = new ArrayList<>();
                        Queue<int[]> queue = new LinkedList<>();
                        queue.add(new int []{i, j});
                        list.add(new int[] {i, j});
                        int cnt = 1;
                        int sum = arr[i][j];
                        visited[i][j] = true;
                        while (!queue.isEmpty()) {
                            int[] loc = queue.poll();
                            int curY = loc[0];
                            int curX = loc[1];
                            for (int d = 0; d < 4; d++) {
                                int y = curY + dy[d];
                                int x = curX + dx[d];
                                if (0 <= y && y < N && 0 <= x && x < N) {
                                    if ((!visited[y][x]) && L <= Math.abs(arr[y][x] - arr[curY][curX]) && Math.abs(arr[y][x] - arr[curY][curX]) <= R) {
                                        changed = true;
                                        sum += arr[y][x];
                                        cnt += 1;
                                        visited[y][x] = true;
                                        queue.add(new int[] {y, x});
                                        list.add(new int[] {y, x});
                                    }
                                }
                            }
                        }
                        for (int[] a : list) {
                            arr[a[0]][a[1]] = sum / cnt;
                        }
                    }
                }
            }
            if (!changed) {
                break;
            }
            days++;
        }
        bw.write(days + "\n");
        bw.flush();
        bw.close();
    }

}