111. 항체 인식 (백준 22352) [JAVA]

문제

문제 링크 : https://www.acmicpc.net/problem/22352

문제

VUNO는 빅데이터와 딥러닝 기술을 통해 학습한 인공지능을 이용해 의학 전문가들의 판단에 도움을 주는 Medical AI 솔루션을 개발하는 전문 기업이다.

VUNO는 최근 SP라는 강력한 새로운 촬영 기법을 개발했다. 이 기법을 사용하면 인체 조직이 격자 형태로 표현되고, 격자의 각 칸에는 해당 부분의 각종 분석 결과를 압축한 하나의 데이터 값이 부여된다. VUNO는 이 SP 촬영 기법을 사용해 CPCU-1202라는 새로운 항체를 연구하려고 한다.

조직에 CPCU-1202 백신을 놓으면, 격자의 칸 중 하나에 항체가 생성된다. 이 항체는 현재 속해 있는 칸과 같은 데이터 값을 가지면서 상하좌우로 인접한 칸이 있을 경우 그 칸으로 퍼져나간다. 이 과정을 계속 반복하다가 항체가 더 이상 퍼져나갈 수 없게 되면, 항체는 조직에 완전히 스며든다. 그 결과로, 항체가 퍼졌던 칸들의 데이터 값은 모두 어떤 동일한 값으로 새로 업데이트된다. 이때, 우연히 원래의 데이터 값과 업데이트된 데이터 값이 동일할 수도 있다.

VUNO의 연구 데이터는 하나의 조직에 백신을 놓기 전의 촬영 결과와 백신을 놓은 뒤의 촬영 결과가 한 쌍으로 이루어져 있다. 두 장의 촬영 결과가 주어질 때, 이 조직에 놓은 백신이 CPCU-1202 백신일 가능성이 있는지 판단하는 프로그램을 작성하라.

입력

첫 번째 줄에는 SP 촬영 결과의 크기를 의미하는 두 정수 $N$과 $M$이 주어진다. ($1 \le N, M \le 30$) 이는 촬영 결과가 세로로 $N$칸, 가로로 $M$칸 크기의 격자라는 것을 의미한다.

다음 $N$개의 줄에는 백신을 놓기 전의 촬영 결과가 주어진다. 각 줄에는 1$1$ 이상 $1\ 000$ 이하의 정수 M$M$개가 공백으로 구분되어 주어지며, $i$번째 줄의 $j$번째 수는 촬영 결과의 $i$번째 행 $j$번째 칸의 데이터 값을 의미한다.

다음 $N$개의 줄에는 백신을 놓은 뒤의 촬영 결과가 위와 동일한 형식으로 주어진다.

출력

촬영 대상이 맞은 백신이 CPCU-1202 백신일 수 있다면 YES, 그럴 수 없다면 NO 를 출력하라.

 

풀이

백신을 맞기 전 -> 후를 비교하는데, 이때 백신이 떨어진 부분으로 추정되는 곳 (1곳)을 타겟으로 BFS를 돌리면 된다.

여기서 유의해야 할 부분이 있는데, 예제로 나온 5번을 확인해보면 우연히 백신을 맞은 부분이 이전 부분과 같아지는 경우이다.

따라서 비교를 어떻게 해야 하냐면

1. 백신을 놓기 전과 후 다른 부분을 찾는다.
2. 백신을 놓은 후 (변화된 부분)를 저장하고 -> 놓기 전 부분을 바꿔준다 (동일한 결과가 나오는지)
3. 이때 놓기 전 부분은 따로 저장하여 BFS 탐색의 조건으로 사용

핵심은 놓기 전 -> 놓은 후 로 바꿔가면서 결과가 같은지 비교하는 것이다.

반대로 놓은 후 -> 놓기 전으로 바꾸려고 하다가 예제 5번과 같은 상황에서 오류가 발생할 수 있다. (뭐로 바뀌는지 모르므로)

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int N, M;
    static int[][] beforeMap;
    static int[][] afterMap;

    static int[] moveX = {1,-1,0,0};
    static int[] moveY = {0,0,1,-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());

        beforeMap = new int[N][M];
        afterMap = new int[N][M];

        for(int i=0; i<N; i++){
           st = new StringTokenizer(br.readLine());
           for(int j=0; j<M; j++){
               beforeMap[i][j] = Integer.parseInt(st.nextToken());
           }
        }
        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<M; j++){
               afterMap[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        start();
        if(check()){
            System.out.println("YES");
        }else {
            System.out.println("NO");
        }

    }
    public static void start(){
        for(int y=0; y<N; y++){
            for(int x=0; x<M; x++){
                if(beforeMap[y][x] != afterMap[y][x]){
                    BFS(x, y, afterMap[y][x]);
                    return;
                }
            }
        }
    }
    public static boolean check(){
        for(int y=0; y<N; y++){
            for(int x=0; x<M; x++){
                if(beforeMap[y][x] != afterMap[y][x]){
                    return false;
                }
            }
        }
        return true;
    }

    public static void BFS(int x, int y, int val){
        Queue<Point> q = new LinkedList<>();
        q.add(new Point(x, y));

        boolean[][] visited = new boolean[N][M];
        visited[y][x] = true;
        //약이 묻은애
        int lastVal = beforeMap[y][x];
        //묻기전
        beforeMap[y][x] = val;

        while (!q.isEmpty()) {
            Point cur = q.poll();

            for (int i = 0; i < 4; i++) {
                int nextX = cur.x + moveX[i];
                int nextY = cur.y + moveY[i];

                if (nextX < 0 || nextX >= M || nextY < 0 || nextY >= N) continue;
                if (!visited[nextY][nextX] &&  beforeMap[nextY][nextX] == lastVal) {
                    q.add(new Point(nextX, nextY));
                    visited[nextY][nextX] = true;
                    beforeMap[nextY][nextX] = val;
                }
            }
        }
    }
}

 

결과