문제 개요
n × n 픽셀 크기의 정사각형 이미지 두 개(first와 second)가 있다고 가정해 보겠습니다. 각 픽셀은 검은색 또는 흰색이며, 이미지는 행렬 형태로 주어집니다. 검은색 픽셀은 'x', 흰색 픽셀은 '.'으로 표현합니다. 이 문제의 목표는 두 번째 이미지를 90° 단위로 회전하거나 평행 이동했을 때 첫 번째 이미지와 완전히 일치하는지 판별하는 것입니다. 일치하면 true를, 그렇지 않으면 false를 반환합니다.
예를 들어 n = 4이고 first = {"..x.", "x.x.", "x.xx", "xx.."}, second = {"..xx", "x.xx", ".x.x", "..x."}가 입력으로 주어지면 결과는 False가 됩니다.
풀이 전략
이 문제는 픽셀 하나하나를 직접 비교하는 대신, 검은색 픽셀('x')의 좌표만 추출하여 비교하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 좌표 수집: 두 이미지에서 각각 'x' 픽셀의 (행, 열) 좌표를 배열에 저장합니다.
- 개수 비교: 검은색 픽셀의 개수가 다르면 어떤 회전이나 이동으로도 일치할 수 없으므로 즉시 false를 반환합니다.
- 평행 이동 검사(find): 두 좌표 배열을 정렬한 뒤, 모든 좌표 쌍이 동일한 오프셋(이동 벡터)만큼 차이가 나는지 확인합니다.
- 회전 검사(rotate): 좌표를 90° 회전 변환한 후 다시 검사하며, 이 과정을 0°, 90°, 180°, 270°의 네 가지 각도에 대해 반복합니다.
- 검은색 픽셀이 하나도 없는 빈 이미지라면 두 이미지는 항상 일치하므로 true를 반환합니다.
위 내용을 의사 코드로 표현하면 다음과 같습니다.
find() 함수 정의 — 쌍(pair) 배열 x, y를 매개변수로 받습니다.
d1 := y[0]의 첫 번째 값 - x[0]의 첫 번째 값
d2 := y[1]의 두 번째 값 - x[1]의 두 번째 값
i := 1부터 x의 크기 미만까지 1씩 증가시키며 반복:
만약 y[i]의 첫 번째 값 - x[i]의 첫 번째 값이 d1과 같지 않거나
y[i]의 두 번째 값 - x[i]의 두 번째 값이 d2와 같지 않으면:
false 반환
true 반환
rotate() 함수 정의 — n, 쌍 배열 a, 쌍 배열 b를 매개변수로 받습니다.
i := 0부터 b의 크기 미만까지 1씩 증가시키며 반복:
b[i] := (b[i]의 두 번째 값, n - b[i]의 첫 번째 값 - 1)
정수 쌍을 저장할 두 배열 a, b 선언
i := 0부터 n 미만까지 1씩 증가시키며 반복:
s := first[i]
j := 0부터 n 미만까지 1씩 증가시키며 반복:
s[j]가 'x'이면:
배열 a의 끝에 쌍(i, j) 추가
i := 0부터 n 미만까지 1씩 증가시키며 반복:
s := second[i]
j := 0부터 n 미만까지 1씩 증가시키며 반복:
s[j]가 'x'이면:
배열 b의 끝에 쌍(i, j) 추가
a의 크기와 b의 크기가 다르면:
false 반환
a의 크기가 0이면:
true 반환
check := false
배열 a 정렬
i := 0부터 4 미만까지 1씩 증가시키며 반복:
배열 b 정렬
find(a, b)가 참이면:
check := true
rotate(n, a, b) 실행
check가 참이면 true 반환, 그렇지 않으면 false 반환예제 구현
더 나은 이해를 돕기 위해 실제 C++ 구현 예제를 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
bool find(vector<pair<int, int>> x, vector<pair<int, int>> y){
int d1 = y[0].first - x[0].first;
int d2 = y[1].second - x[1].second;
for(int i = 1; i < x.size(); i++){
if(y[i].first - x[i].first != d1 || y[i].second - x[i].second != d2){
return false;
}
}
return true;
}
void rotate(int n, vector<pair<int, int>> a, vector<pair<int, int>> b){
for(int i = 0; i < b.size(); i++){
b[i] = make_pair(b[i].second, n - b[i].first - 1);
}
}
bool solve(int n, vector<string> first, vector<string> second){
vector<pair<int, int>> a, b;
for(int i = 0; i < n; i++){
string s = first[i];
for(int j = 0; j < n; j++){
if(s[j] == 'x'){
a.push_back(make_pair(i, j));
}
}
}
for(int i = 0; i < n; i++){
string s = second[i];
for(int j = 0; j < n; j++){
if(s[j] == 'x'){
b.push_back(make_pair(i, j));
}
}
}
if(a.size() != b.size()){
return false;
}
if(a.size() == 0){
return true;
}
bool check = false;
sort(a.begin(), a.end());
for(int i = 0; i < 4; i++){
sort(b.begin(), b.end());
if(find(a, b)){
check = true;
}
rotate(n, a, b);
}
if(check){
return true;
}else{
return false;
}
}
int main() {
int n = 4;
vector<string> first = {"..x.", "x.x.", "x.xx", "xx.."}, second = {"..xx", "x.xx", ".x.x", "..x."};
cout << solve(n, first, second);
return 0;
}입력
4, {"..x.", "x.x.", "x.xx", "xx.."}, {"..xx", "x.xx", ".x.x", "..x."}출력
0
실행 결과로 0(false)이 출력되었습니다. 이는 두 번째 이미지가 어떠한 회전과 평행 이동의 조합으로도 첫 번째 이미지와 일치하지 않음을 의미합니다.