죽지도 않고 다시 온 알고리즘 풀이 (꾸준히 좀 해 제발)
👀 문제
22352번: 항체 인식 ✨ 골드 5
VUNO는 빅데이터와 딥러닝 기술을 통해 학습한 인공지능을 이용해 의학 전문가들의 판단에 도움을 주는 Medical AI 솔루션을 개발하는 전문 기업이다.
VUNO는 최근 SP라는 강력한 새로운 촬영 기법을 개발했다. 이 기법을 사용하면 인체 조직이 격자 형태로 표현되고, 격자의 각 칸에는 해당 부분의 각종 분석 결과를 압축한 하나의 데이터 값이 부여된다. VUNO는 이 SP 촬영 기법을 사용해 CPCU-1202라는 새로운 항체를 연구하려고 한다.
조직에 CPCU-1202 백신을 놓으면, 격자의 칸 중 하나에 항체가 생성된다. 이 항체는 현재 속해 있는 칸과 같은 데이터 값을 가지면서 상하좌우로 인접한 칸이 있을 경우 그 칸으로 퍼져나간다. 이 과정을 계속 반복하다가 항체가 더 이상 퍼져나갈 수 없게 되면, 항체는 조직에 완전히 스며든다. 그 결과로, 항체가 퍼졌던 칸들의 데이터 값은 모두 어떤 동일한 값으로 새로 업데이트된다. 이때, 우연히 원래의 데이터 값과 업데이트된 데이터 값이 동일할 수도 있다.
VUNO의 연구 데이터는 하나의 조직에 백신을 놓기 전의 촬영 결과와 백신을 놓은 뒤의 촬영 결과가 한 쌍으로 이루어져 있다. 두 장의 촬영 결과가 주어질 때, 이 조직에 놓은 백신이 CPCU-1202 백신일 가능성이 있는지 판단하는 프로그램을 작성하라.
예제 입력
4 4
2 2 2 1
2 2 1 3
2 1 3 3
1 3 3 3
4 4 4 1
4 4 1 3
4 1 3 3
1 3 3 3예제 출력
YES🔑 키포인트
그래프 이론 그래프 탐색 깊이 우선 탐색
✍️ 코드
📍 dfs를 이용해 데이터 그룹을 파악하고, 한 그룹이 발견되면 백신을 놓은 이후의 모습과 비교하여 달라짐 / 동일함 / 그룹이 아님 세 가지로 구분하여 결과를 도출해낸다.
💡 나는 YES/NO인 경우를 아래와 같이 정리하였다.
☺️ YES
➡️ 데이터 달라진 그룹이 딱 한 개인 경우. (해당 그룹의 한 조직에 백신 놓았다고 생각할 수 있음)
➡️ 데이터 달라진 그룹은 0개, 동일한 그룹은 1개 이상. (해당 그룹들 중 하나의 조직에 백신 놓았다고 생각할 수 있음)
😤 NO
➡️ 데이터 그룹이 동일하지 않은 경우.
➡️ 데이터가 달라진 그룹이 여러개인 경우. '하나의' 조직에 백신을 넣은 게 아니기 때문.
✌️ 나의 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class BOJ22352_항체인식 {
static int n, m;
static boolean[][] visited;
static int[][] before, after;
static int[] dx = { -1, 1, 0, 0 };
static int[] dy = { 0, 0, -1, 1 };
static boolean flag;
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];
after = new int[n][m];
visited = new boolean[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());
}
}
// 백신 놓은 후
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());
}
}
// dfs 돌면서 확인
int sameCnt = 0;
int diffCnt = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (visited[i][j]) {
continue;
}
flag = true; // 플래그 초기화
visited[i][j] = true; // 시작 지점 방문 처리
dfs(i, j);
if (!flag) {
// 그룹이 동일하지 않다면 바로 "NO" 반환.
System.out.println("NO");
return;
}
if (before[i][j] == after[i][j]) {
sameCnt++; // 이전, 이후 데이터 같은 경우
} else {
diffCnt++; // 이전, 이후 데이터 달라진 경우
}
}
}
/**
* "YES"인 경우
* 1. 데이터 달라진 그룹이 딱 한 개인 경우. (해당 그룹의 한 조직에 백신 놓았다고 생각할 수 있음)
* 2. 데이터 달라진 그룹은 0개, 동일한 그룹은 1개 이상. (해당 그룹들 중 하나의 조직에 백신 놓았다고 생각할 수 있음)
*
* "NO"인 경우
* 1. 데이터 그룹이 동일하지 않은 경우.
* 2. 데이터가 달라진 그룹이 여러개인 경우. '하나의' 조직에 백신을 넣은 게 아니기 때문.
*/
if (diffCnt == 1 || (diffCnt == 0 && sameCnt >= 1)) {
System.out.println("YES");
} else {
System.out.println("NO");
}
}
static void dfs(int x, int y) {
// 상하좌우 이동
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) {
// 데이터가 동일하며, 방문하지 않은 경우
if (before[x][y] == before[nx][ny] && !visited[nx][ny]) {
visited[nx][ny] = true; // 방문 처리 (중복 방지)
// 이전엔 그룹에 포함되지만 이후에는 그룹이 아니게 됐다면 CPCU-1202 백신이 아니기애 false 리턴.
if (after[x][y] != after[nx][ny]) {
flag = false;
return;
}
dfs(nx, ny);
}
}
}
}
}