[BOJ] 백준 2160 그림 비교

출처: https://www.acmicpc.net/problem/2160

 Input 

3

..X....

.XXX...

.XX....

.....X.

.X...X.

...X...

..XX...

.XX....

.XX..X.

.X...X.

XX.....

X......

XX...XX

XXXX.XX

XXX..XX

 

 Output 

1 2

ex) n = 5 일 때, 아래와 같이 비교대상을 두어 완전탐색

▷ 1 = { 2, 3, 4, 5 }

▷ 2 = { 3, 4, 5 }

▷ 3 = { 4, 5 }

▷ 4 = { 5 }

 

---

#include <iostream>
#include <string>
using namespace std;
#define MAX 987654321
 
char map[5][7][50];
string str;
int firstPicture, secondPicture, cnt, answer = MAX;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    int n; cin >> n;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < 5; ++j) {
            cin >> str;
            for (int k = 0; k < 7; ++k) {
                map[j][k][i] = str[k];
            }
        }
    }
 
 
    for (int pivot = 0; pivot < n; ++pivot) {
        for (int target = pivot + 1; target < n; ++target) {
            cnt = 0;
            for (int i = 0; i < 5; ++i) {
                for (int j = 0; j < 7; ++j) {
                    if (map[i][j][pivot] != map[i][j][target]) cnt++;
                    // 기존값보다 크면 탐색 무의미
                    if (cnt > answer) break;
                }
                // 기존값보다 크면 탐색 무의미
                if (cnt > answer) break;
            }
 
            if (cnt < answer) {
                answer = cnt;
                firstPicture = pivot + 1;
                secondPicture = target + 1;
            }
        }
    }
 
    cout << firstPicture << " " << secondPicture << endl;
 
}