[Baekjoon] 22352_항체 인식

Gold V

문제(출처: https://www.acmicpc.net/problem/22352)

---

< 항체 인식 >

 

문제 풀이

 

백신을 놓기 전과 놓은 뒤의 촬영 결과가 다른 곳을 먼저 찾아 배열에 저장해 둡니다. 

그 후에 변화한 값을 기준으로 bfs를 활용하여 항체가 퍼진 곳인지 찾아 줍니다.

bfs로 주변을 다 탐색한 후에도 변화한 값이 존재한다면 맞은 백신이 CPCU-1202가 아니므로 "NO"를 출력하고,

다 탐색한 후에 변화한 값이 존재하지 않는다면 "YES"를 출력해 줍니다.

 

 

 

 - my solution (Java)

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

public class _22352_ { // 항체 인식
	static int arr[][], diff[][], n , m;
	static boolean visited[][], flag;
	static int dx[]= {-1,1,0,0};
	static int dy[]= {0,0,-1,1};
	public static void main(String[] args) throws IOException {
		BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(bf.readLine());

		n=Integer.parseInt(st.nextToken()); // 세로
		m=Integer.parseInt(st.nextToken()); // 가로

		arr=new int[n][m];
		diff=new int[n][m];
		visited=new boolean[n][m];
		flag= false;

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

		int start_x=-1, start_y=-1;
		for(int i=0; i<n; i++) {
			st=new StringTokenizer(bf.readLine());
			for(int j=0; j<m; j++) {
				int num=Integer.parseInt(st.nextToken());
				if( arr[i][j] != num) {
					diff[i][j]=num;
					if(start_x==-1 && start_y==-1) {
						start_x=i;
						start_y=j;
					}
				}
			}
		}
		if(start_x!= -1 && start_y != -1) search(start_x, start_y);

		for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++) {
				if(diff[i][j]>0) {
					flag=true;
					break;
				}
			}
		}

		if(flag) System.out.println("NO");
		else System.out.println("YES");
	}
	private static void search(int start_x, int start_y) {
		Queue<int[]>queue=new LinkedList<>();
		queue.add(new int[] {start_x, start_y});
		visited[start_x][start_y]=true;
		int num=diff[start_x][start_y];
		diff[start_x][start_y]=0;

		while(!queue.isEmpty()) {
			int temp[]=queue.poll();
			for(int i=0; i<4; i++) {
				int x=temp[0]+dx[i];
				int y=temp[1]+dy[i];
				if(x>=0 && x<n && y>=0 && y<m && !visited[x][y] && arr[temp[0]][temp[1]]==arr[x][y]) {
					if(diff[x][y]==num || (diff[x][y]==0 && arr[x][y]==num)) {
						visited[x][y]=true;
						diff[x][y]=0;
						queue.add(new int[] {x,y});
					}else {
						flag=true;
						break;
					}
				}
			}
			if(flag) break;
		}
	}
}

 

Main

-  세로 (n), 가로 (m) 입력

- arr : 백신을 놓기 전의 촬영 결과 입력

- diff : 백신을 놓기 전과 놓은 후 달라진 값만 저장

- start_x, start_y : 백신을 놓기 전과 놓은 후 달라진 값 중 bfs를 시작할 위치 저장

- start_x와 start_y가 -1이면 촬영 전과 촬영 후가 같다는 뜻이므로 search 함수 호출 x, -1이 아니면 search 함수 호출

- search 함수 호출 후에도 diff에 0보다 큰 값이 있다면 CPCU-1202 백신이 아니라는 뜻이므로 flag를 true로 바꿈

- flag 값에 따라 NO와 YES 출력

 

Search

- queue가 빌 때까지 반복하면서 값을 하나 뽑아 상하좌우 탐색

- 상하좌우 값이 범위 안이며 아직 방문하지 않은 곳이며 현재 속해있는 칸과 같은 데이터 값을 가진다면

   -> 백신을 놓은 뒤 현재 값과 상하좌우 이동한 값이 같거나, 값이 변하지 않았으며 백신 놓은 뒤 현재 값과 같다면 방문 표시 및 diff 값도 0으로 바꾼 후 queue에 추가

  -> 위 상황이 아니라면 flag를 true로 변환 후 탈출

 

---

생각🤔

 

바뀐 값을 잘 고려하여 bfs를 활용하면 쉽게 해결할 수 있었다.

---