항체 인식 - 22352

문제

풀이

import java.util.Scanner;

// 항체 인식 - G5 - DFS
public class ex22352 {

    static int n,m;
    static int[][] board;
    static int[][] compare;
    static boolean flag=false;
    static String answer="YES";
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int[] diffInfo = new int[4];


    public static void DFS(int x,int y,int before, int after){
        board[x][y]=after;
        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx>=0 && nx<n && ny>=0 && ny<m && board[nx][ny]==before){
                DFS(nx,ny,before,after);
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();

        board = new int[n][m];
        compare = new int[n][m];

        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                board[i][j]=sc.nextInt();
            }
        }

        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                compare[i][j] = sc.nextInt();
                if(compare[i][j]!=board[i][j] && !flag){
                    flag=true;
                    diffInfo[0] = i;
                    diffInfo[1] = j;
                    diffInfo[2] = board[i][j];
                    diffInfo[3] = compare[i][j];
                }
            }
        }

        if(flag) DFS(diffInfo[0],diffInfo[1],diffInfo[2],diffInfo[3]);

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

이 문제 풀이 방식은 되게 신기했다. 색다른 자극,,
백신 접종이 한 번 가능한데, 접종 이후에도 두 board,compare가 다른 정보를 가지고 있으면 정답은 "NO"가 출력되어야한다.

처음에 compare[][]를 입력받을 때 board[][]와의 정보 차이를 diffInfo[]에 저장해두고 DFS()를 호출해서 해당 board[][]에 compare[][]의 값을 접종해준다. 이 때 두번이상 접종이 되면 안되기 때문에 boolean 타입의 변수를 사용해줘야 한다. 중요!