[백준] 22352: 항체 인식 - JAVA

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

 

풀이

숫자로 채워진 N x M 크기의 격자가 2개 주어진다.

 

첫 번째 격자를 before, 두 번째 격자를 after라는 이름으로 이차원 배열에 저장했다.

 

문제의 내용은 before의 어떤 한 점에 백신을 놓는다면, 인접한 영역 중 같은 숫자의 영역들이 함께 동일한 값으로 업테이트 된다는 것이다.

 

업데이트 하였을 때 입력에서 주어진 after와 같으면 YES, 다르면 NO를 출력하면 된다.

 

(0, 0) 부터 순회하면서 before와 after가 처음으로 달라지는 부분을 찾았다. 해당부분부터 bfs탐색을 통해 인접한 같은 값의 영역들을 after에 해당하는 값으로 바꿔주었다.

 

그 후, 다시 (0, 0) 부터 before와 after를 비교하여 같은지 확인했다.

 

처음에는 다시 처음부터 비교하지 않고, bfs탐색을 한 지점부터 비교를 했는데 틀렸다고 나왔다.

 

이미 지나온 값이 변경되어 after와 달라질 수 있기 때문에 처음부터 비교를 해주어야 한다.

 

---

 

메모리: 14496KB
시간: 112ms
언어: Java 11

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

public class Main {
    static int n, m;
    static int[][] before, after;

    static int[][] vector = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };

    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());
        m = Integer.parseInt(st.nextToken());

        before = new int[n][m];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                before[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        after = new int[n][m];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                after[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        loop: for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (before[i][j] != after[i][j]) {
                    injectVaccine(i, j, after[i][j]);
                    break loop;
                }
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (before[i][j] != after[i][j]) {
                    System.out.println("NO");
                    return;
                }
            }
        }

        System.out.println("YES");
    }

    private static void injectVaccine(int r, int c, int vac) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[] { r, c });

        List<int[]> list = new ArrayList<>();
        list.add(new int[] { r, c });

        boolean[][] visited = new boolean[n][m];
        visited[r][c] = true;

        while (!queue.isEmpty()) {
            int[] node = queue.poll();

            for (int k = 0; k < 4; k++) {
                int nr = node[0] + vector[k][0];
                int nc = node[1] + vector[k][1];

                if (nr < 0 || nc < 0 || nr >= n || nc >= m) {
                    continue;
                }

                if (visited[nr][nc]) {
                    continue;
                }

                if (before[nr][nc] != before[r][c]) {
                    continue;
                }

                queue.add(new int[] { nr, nc });
                list.add(new int[] { nr, nc });
                visited[nr][nc] = true;
            }
        }

        for (int[] node : list) {
            before[node[0]][node[1]] = vac;
        }
    }

}