문제 링크입니다: https://www.acmicpc.net/problem/1080
그리디(Greedy) 알고리즘을 적용하여 좌측 상단의 인덱스부터 비교해가며 주어진 행렬에서 결과 행렬로 바뀔 수 있는지 판별하는 문제였습니다.
알고리즘은 아래와 같습니다.
1. N과 M이 모두 3 이상일 때만 XOR 연산을 할 수 있기 때문에 N이나 M 중 하나라도 3 미만이라면 서로 같은지만 판별한다.
2. N과 M이 모두 3 이상이라면 좌측 상단 부터 해당 인덱스에 있는 값들을 비교하고 만약 서로가 다르다면 XOR 연산을 진행합니다.
i) 비교해갈 때 y축은 N-3까지 x축은 M-3까지 for문을 돌립니다.
ii) 만약 XOR 연산을 진행하고 난 뒤 결과 행렬과 동일하다면 반복문을 빠져나와 XOR 연산 횟수를 출력합니다.
iii) 반복문을 모두 돌아도 결과 행렬과 같지 않다면 -1을 출력합니다.
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
const int MAX = 50;
const int INF = 987654321;
int N, M;
bool arr[MAX][MAX];
bool result[MAX][MAX];
//3*3 XOR 연산
void XOR(int y, int x)
{
for (int i = y; i < y + 3; i++)
for (int j = x; j < x + 3; j++)
{
int temp = arr[i][j];
arr[i][j] = 1 - temp;
}
}
int main(void)
{
ios_base::sync_with_stdio(0);
cin.tie(0); //cin 실행속도 향상
cin >> N >> M;
for (int i = 0; i < N; i++)
{
string temp;
cin >> temp;
for (int j = 0; j < temp.length(); j++)
if (temp[j] == '0')
arr[i][j] = 0;
else
arr[i][j] = 1;
}
for (int i = 0; i < N; i++)
{
string temp;
cin >> temp;
for (int j = 0; j < temp.length(); j++)
if (temp[j] == '0')
result[i][j] = 0;
else
result[i][j] = 1;
}
int cnt = 0;
bool change = false;
//XOR 함수를 적용할 수 있는 경우는 가로 세로 각각 3 이상
if (N >= 3 && M >= 3)
{
for (int i = 0; i <= N - 3; i++)
{
for (int j = 0; j <= M - 3; j++)
{
//해당 인덱스에서 같지 않으면 XOR 함수 호출
if (arr[i][j] != result[i][j])
{
XOR(i, j);
cnt++;
}
//이제 해당 행렬과 결과 행렬이 같은지 판별
bool same = true;
for (int y = 0; y < N; y++)
{
for (int x = 0; x < M; x++)
if (arr[y][x] != result[y][x])
{
same = false;
break;
}
}
if (same == true)
{
//같다면 바뀌었다고 표시하고 break
change = true;
break;
}
}
if (change) //같다면 break
break;
}
}
//N이나 M이 3 이하이면 서로 같은지 판별
else
{
change = true;
for (int y = 0; y < N; y++)
for (int x = 0; x < M; x++)
if (arr[y][x] != result[y][x])
change = false;
}
if (change)
cout << cnt << "\n";
else
cout << -1 << "\n";
return 0;
}
개발환경:Visual Studio 2017
지적, 조언, 질문 환영입니다! 댓글 남겨주세요~
'알고리즘 > BOJ' 카테고리의 다른 글
백준 1377번 버블 소트 (0) | 2018.07.24 |
---|---|
백준 2873번 롤러코스터 (4) | 2018.07.23 |
백준 10610번 30 (6) | 2018.07.23 |
백준 2875번 대회 or 인턴 (7) | 2018.07.23 |
백준 14889번 스타트와 링크 (2) | 2018.07.23 |