[Baekjoon - 22352] 항체 인식

난이도: Gold V

 

태그

• Depth-First Search

 

풀이

1. (y, x)에 값 a의 백신을 투여한다면?

(y, x)와 연결된 위치들의 값들을 DFS를 돌려가면서 a로 바꿔주면 됩니다.

DFS 한 번으로 백신을 놓는 시뮬레이션을 할 수 있다는 의미죠.

 

2. 백신을 투여했다고 확신할 수 있는 위치는?

백신 투여 이전과 이후의 값이 달라진 위치가 있다면, 그 위치는 반드시 백신의 영향을 받은 위치가 되죠.

하나의 연결 요소에 대해서, 연결 요소의 어느 위치에 백신을 놓든 결과는 동일하기 때문에

그냥 그 위치에 백신을 놓았다 라고 가정하고, 시뮬레이션을 돌려준 뒤, 실제 결과랑 비교해주면 됩니다.

 

만약 이전과 이후의 차이가 없다면, 그냥 적당한 위치에 이전/이후의 값이 동일한 백신을 놓았다고 볼 수 있습니다.

 

3. 구현 디테일

아래 코드에서는, 몇몇가지 사실을 사용해서 DFS를 간단히 돌립니다.

• 이전과 이후의 차이가 반드시 있으므로, visited[y][x]를 따로 관리할 필요 없이
  그냥 map[y][x]의 값이 이전 값이랑 동일한지만 보면 됩니다.
• 격자판 바깥으로 나가는 경우는, 격자판 바깥의 값이 기본값 (0)으로 초기화되어있다면
  격자판 안에 있는 값들은 1 이상이기 때문에 알아서 걸러집니다.

 

4. 코드

int mp1[32][32], mp2[32][32];
void dfs(int y, int x, int v, int w){
    mp1[y][x] = w;
    for (int d = 0; d < 4; d++){
        int yy = y+dy[d], xx = x+dx[d];
        if (mp1[yy][xx] == v){ dfs(yy, xx, v, w); }
    }
}
 
void Main(){
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){ cin >> mp1[i][j]; }
    }
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){ cin >> mp2[i][j]; }
    }
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            if (mp1[i][j] != mp2[i][j]){
                dfs(i, j, mp1[i][j], mp2[i][j]);
                for (int y = 1; y <= n; y++){
                    for (int x = 1; x <= m; x++){
                        if (mp1[y][x] != mp2[y][x]){ cout << "NO"; return; }
                    }
                }
                cout << "YES"; return;
            }
        }
    }
    cout << "YES";
}