22352 항체 인식

처음에 문제 이해를 못해서 조금 애먹었다. 주사를 놓으면 구역이 특정 숫자로 바뀌는데 그게 백신인지 맞추라고??? 특정 숫자로 바뀌는데 뭐 어쩌라고 싶었다. 알고보니 그냥 범위에 맞게 바뀌는지 확인하는게 목적인 것 같다. 

 

처음에 든 생각은 1번 사진이랑 2번 사진을 한 칸씩 비교하는데 다른 숫자가 나오면 그 숫자를 기준으로 dfs를 돌려서 같은 숫자 범위에 백신을 맞게 한다. 그 다음 또 다른 숫자가 나오고 그게 백신을 맞지 않은 범위라면 NO를 출력하고 아니면 YES를 출력하게 했다. 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>
#include <stdio.h>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using iis = pair<int, string>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;

int map1[35][35];
int map2[35][35];

int n, m;
bool visited[35][35];

int dx[] = { 1, 0, -1, 0 };
int dy[] = { 0, 1, 0, -1 };

void dfs(int y, int x, int startValue)
{
    visited[y][x] = true;

    for (int i = 0; i < 4; i++)
    {
        if (x + dx[i] < 0 || m <= x + dx[i])
            continue;
        if (y + dy[i] < 0 || n <= y + dy[i])
            continue;

        if (map1[y + dy[i]][x + dx[i]] != startValue)
            continue;

        if (visited[y + dy[i]][x + dx[i]])
            continue;

        dfs(y + dy[i], x + dx[i], startValue);
    }
}

int main() {
    scanf("%d %d", &n, &m);
    
    memset(visited, false, sizeof(visited));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &map1[i][j]);
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &map2[i][j]);
        }
    }
    
    bool checkDfs = false;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (map1[i][j] != map2[i][j] && visited[i][j] == true) {
                continue;
            }
            
            if (map1[i][j] != map2[i][j] && !visited[i][j] && !checkDfs) {
                dfs(i, j, map1[i][j]);
                checkDfs = true;
            } else if (map1[i][j] != map2[i][j] && !visited[i][j] && checkDfs) {
                printf("NO\n");
                return 0;
            }
        }
    }
    
    printf("YES\n");
    
    return 0;
}

 

코드는 이렇게 짰다. 그런데 틀렸다. 어디서 틀린지 예시를 계속 넣어봤는데 그래도 못 찾아서 결국에는 코드 갈아엎고 다시 짰다. 

 

두 번째 방법은 정말로 백신을 맞은 결과를 만든다음 그게 2번째 사진이랑 같은지 비교한다. 

 

- 1번 사진이랑 같은 tmp 사진을 만듬

- 1번과 2번이 다르다면 그 숫자를 tmp에 백신을 맞힘

- 한 번 백신을 맞았다면 다음부터는 체크하지 않음

- 마지막으로 2번 사진과 tmp 사진이 같은지 비교한다

 

코드는 이렇다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>
#include <stdio.h>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using iis = pair<int, string>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;

int map1[35][35];
int tmpMap[35][35];
int map2[35][35];

int n, m;
bool visited[35][35];

int dx[] = { 1, 0, -1, 0 };
int dy[] = { 0, 1, 0, -1 };

void dfs(int y, int x, int map1Val, int map2Val)
{
    visited[y][x] = true;
    tmpMap[y][x] = map2Val;
    
    for (int i = 0; i < 4; i++)
    {
        int test = 0;
        if (x + dx[i] < 0 || m <= x + dx[i])
            continue;
        if (y + dy[i] < 0 || n <= y + dy[i])
            continue;
        if (map1[y + dy[i]][x + dx[i]] != map1Val)
            continue;
        if (visited[y + dy[i]][x + dx[i]])
            continue;
        dfs(y + dy[i], x + dx[i], map1Val, map2Val);
    }
}

int main() {
    scanf("%d %d", &n, &m);
    
    memset(visited, false, sizeof(visited));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &map1[i][j]);
            tmpMap[i][j] = map1[i][j];
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &map2[i][j]);
        }
    }
    
    bool checkDfs = false;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (map1[i][j] == map2[i][j])
                continue;
            
            if (checkDfs)
                continue;
           
            dfs(i, j, map1[i][j], map2[i][j]);
            checkDfs = true;
        }
    }
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (tmpMap[i][j] != map2[i][j]) {
                printf("NO\n");
                return 0;
            }
        }
    }
    
    printf("YES\n");
    
    return 0;
}

다행히도 통과했다!!

 

이전 코드에 뭔가 예외가 있었나보다. 바로 다른 풀이라도 짜서 다행이구만 ~.~