[백준] 22352 항체 인식 / 자바(Java)

문제

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

22352번: 항체 인식

 

---

해설

문제에 나오는 CPCU-1202 백신은 2차원 배열 중 단 한곳에 떨어지고, 그 떨어진 곳과 인접하며 같은 숫자인 위치로 퍼지며 모두 퍼지게 된 이후에 함께 어떤 특정 값으로 바뀌는 특징이 있습니다.

 

문제의 입력값은 2차원 배열의 이전 모습과 이후 모습을 주며 해당 백신이 들어갔을 가능성이 있는가를 파악하는 것이 문제입니다.

 

문제의 풀이방식은 2차원 배열의 4방탐색이면 충분하지만 문제해결을 위한 조건을 따져보아야 합니다.

 

백신의 특성을 보고 조건들을 뽑아보면

1. 단 한곳에 떨어진다.

2. 인접하며 같은 숫자인 위치로 퍼진다.

3. 어떤 특정 값으로 바뀐다.

3가지를 확인할 수 있습니다.

 

1. 단 한곳에 떨어진다.

 

한 곳에 떨어지기 때문에 입력을 받을 때 2차원 배열에서 다른 마지막 부분을 저장하면 만약 백신이 적용되었다면 그 곳에서 시작되어 퍼진 부분이 유일한 다른 점임을 보장할 수 있습니다.

 

2. 인접하며 같은 숫자인 위치로 퍼진다.

 

4방탐색을 통해 동일한 숫자이며 인접한 값들을 찾아 이후 모습의 시작위치와 같은 값의 숫자로 바꿔줍니다.

이 과정을 거치면 이전모습과 이후모습이 동일한지 확인해 1.을 근거로 백신 적용 여부를 확인합니다.

 

3. 어떤 특정 값으로 바뀐다.

 

어떤 특정 값으로 바뀌는 것은 동일한 값으로 바뀔 수 있음을 내포합니다. 따라서 처음 입력받을 때 다른 부분이 없다면 추가 연산없이 true로 return하는 과정을 추가해야 합니다.

 

주의점

• 백신이 떨어졌지만 동일한 값으로 바뀔 수 있다(이전 모습과 이후 모습이 동일하더라도 백신이 적용된 모습이다.)

---

코드

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

public class Main{

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int r = Integer.parseInt(st.nextToken());
		int c = Integer.parseInt(st.nextToken());
		
		int before[][] = new int [r][c];
		int after[][] = new int [r][c];
		
		for(int i=0;i<r;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<c;j++) {
				before[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		for(int i=0;i<r;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<c;j++) {
				after[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		int point[] = new int [2];
		int afternum=0;
		boolean flag=false;
		for(int i=0;i<r;i++) {
			for(int j=0;j<c;j++) {
				if(before[i][j]!=after[i][j]) {
					point[0] = i; 
					point[1] = j;
					afternum = after[i][j];
					flag=true;
					break;
				}
			}
			if(flag) break;
		}
		if(!flag) {
			System.out.println("YES");
			System.exit(0);
		}
		// 4방탐색하며 주변 같은 색을 전부 지움
		int dr [] = {-1,0,1,0};
		int dc [] = {0,1,0,-1};
		dfs(before, before[point[0]][point[1]], dr, dc, point[0], point[1],afternum);
		
		flag = false;
		for(int i=0;i<r;i++) {
			for(int j=0;j<c;j++) {
				if(before[i][j]!=after[i][j]) {
					System.out.println("NO");
					flag=true;
					break;
				}
			}
			if(flag) break;
		}
		
		if(!flag) System.out.println("YES");
	}
	
	static void dfs(int after[][], int target, int [] dr, int [] dc, int r, int c, int afternum) {
		after[r][c] = afternum;
		for(int i=0;i<4;i++) {
			int newr = r+dr[i];
			int newc = c+dc[i];
			
			if(newr<0 || newc<0 || newr>=after.length || newc >= after[0].length) continue;
			
			if(after[newr][newc]!=target)continue;
			
			dfs(after, target, dr, dc, newr, newc, afternum);
		}
	}
}