[BOJ/Silver 1] 백준 30702 국기 색칠하기(C++)

문제 링크

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

30702번: 국기 색칠하기

 

문제

세계의 여러 나라들은 자신의 나라를 상징하는 깃발인 국기가 있는데, 그중에는 색만 다르고 모양이 비슷한 국기들이 있다. 국기는 N행 M열의 격자판(행렬)으로 구성되어 있다. 격자판의 각 칸을 이루는 색은 A부터 Z까지의 영어 알파벳 대문자로 표현한다.

 A[i][j]를 국기 A의 i행 j열의 색이라고 하자. 두 국기 A, B 가 주어졌을 때, 모든 i, j(1 ≤ i ≤ N; 1 ≤ j ≤ M)에 대해 A[i][j]와 B[i][j]가 같으면 둘은 같은 국기이다.

근호는 국기 A와 B를 가지고 있고, 국기 A를 적절히 색칠하여 국기 B와 같게 만들려고 한다. 국기를 색칠할 때는 다음과 같은 동작을 0회 이상 반복한다.

• 국기의 격자판 중 한 칸을 고르고, 이 칸과 같은 구역에 속한 모든 칸을 찾는다. 두 칸이 같은 색이면서 상하좌우로 인접해 있을 경우 둘은 같은 구역에 속한다. 이후, 해당하는 구역의 칸들의 색을 원하는 다른 색으로 바꾼다. 이 때, 영어 알파벳 대문자 외에도 임의의 다른 색을 새로 사용할 수 있다.

 

근호가 가진 국기 두 장의 정보가 주어졌을 때, 국기 A를 적절히 색칠해 국기 B와 똑같이 만들 수 있는지 판별하여라. 국기를 돌리거나 뒤집을 수는 없음에 유의하라.

 

입력

첫 번째 줄에 국기의 행 개수 N과 열 개수 M이 공백으로 구분되어 정수로 주어진다.(3 ≤ N, M ≤ 50)

이후 N개의 줄에는 국기 A의 각 칸을 이루는 색이 줄마다 길이 M의 문자열로 주어진다. 이 중 i번째 줄의 j번째 문자가 A[i][j]를 나타낸다. 각 문자열은 영어 알파벳 대문자로만 이루어져 있다.

그다음 N개의 줄에는 국기 B의 각 칸을 이루는 색이 위와 동일한 형식으로 주어진다.

 

출력

국기 A를 적절히 색칠하여 국기 B와 같게 만들 수 있으면 YES를, 그렇지 않으면 NO를 출력한다.

 

예제 입력 1

3 6
AABBCC
AABBCC
AABBCC
DDEEFF
DDEEFF
DDEEFF

예제 출력 1

YES

예제 입력 2

3 4
AAAA
BBBB
CCCC
DEEF
DEEF
DEEF

예제 출력 2

NO

 

알고리즘 분류

• 그래프 탐색

 

풀이

A[0][0]부터 BFS를 수행하는데 이 때 국기 A와 B를 따로 탐색하며 방문한 칸에 방문했음을 기록한다.

그리고 국기 A의 A[0][0]이 속한 구역의 모든 칸에 대하여 국기 B도 해당 칸을 방문했는지를 비교한다.

구역의 모든 칸에 대하여 국기 B의 해당 칸도 같은 구역에 속한다면 임의의다른 색을 칠하여 국기 B를 국기 A로 만들 수 있다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#define MAX 51
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N, M;
char A[MAX][MAX], B[MAX][MAX];
bool VisitedA[MAX][MAX], VisitedB[MAX][MAX];
int MoveY[4] = { -1,0,1,0 };
int MoveX[4] = { 0,-1,0,1 };
bool Answer = true;

void init() {
    for (int i = 0; i < MAX; i++) {
        for (int j = 0; j < MAX; j++) {
            VisitedA[i][j] = false;
            VisitedB[i][j] = false;
        }
    }
}

void input() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> A[i][j];
        }
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> B[i][j];
        }
    }
}

void BFS(int Y, int X) {
    queue<pair<int, int> > Q;
    VisitedA[Y][X] = true;
    Q.push(make_pair(Y, X));

    while (!Q.empty()) {
        int NowY = Q.front().first;
        int NowX = Q.front().second;
        Q.pop();

        for (int i = 0; i < 4; i++) {
            int NextY = NowY + MoveY[i];
            int NextX = NowX + MoveX[i];
            if ((NextY >= 0) && (NextY < N) && (NextX >= 0) && (NextX < M) && !VisitedA[NextY][NextX] && (A[NowY][NowX] == A[NextY][NextX])) {
                VisitedA[NextY][NextX] = true;
                Q.push(make_pair(NextY, NextX));
            }
        }
    };

    VisitedB[Y][X] = true;
    Q.push(make_pair(Y, X));

    while (!Q.empty()) {
        int NowY = Q.front().first;
        int NowX = Q.front().second;
        Q.pop();

        for (int i = 0; i < 4; i++) {
            int NextY = NowY + MoveY[i];
            int NextX = NowX + MoveX[i];
            if ((NextY >= 0) && (NextY < N) && (NextX >= 0) && (NextX < M) && !VisitedB[NextY][NextX] && (B[NowY][NowX] == B[NextY][NextX])) {
                VisitedB[NextY][NextX] = true;
                Q.push(make_pair(NextY, NextX));
            }
        }
    };
}

bool compare() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (VisitedA[i][j]) {
                if (VisitedA[i][j] != VisitedB[i][j]) {
                    return false;
                }
            }
        }
    }

    return true;
}

void settings() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            init();
            BFS(i, j);
            if (!compare()) {
                Answer = false;
                break;
            }
        }
    }
}

void find_Answer() {
    if (Answer) {
        cout << "YES\n";
    }
    else {
        cout << "NO\n";
    }
}

int main() {
    FASTIO
    input();
    settings();
    find_Answer();

    return 0;
}