[백준] 1411번 비슷한 단어 (C++)

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

 

 

이 문제는 N개의 문자열의 개수가 주어지고 서로 다른 문자가 주어졌을때 비슷한 단어의 쌍을 출력하는 문제이다.

비슷한 단어란 단어를 변경할 수 있는데 만약 하나의 알파벳을 다른것으로 변경한 경우 문자열에서의 변경했던 단어가 모든 문자에 대해 변경된다.

 

이때 문자열을 변경했을때 둘이 같은 경우 비슷한 단어라고 한다.

 

 

문자의 길이가 최대 100이다 N의 크기가 최대 몇인지는 모르겠지만 완전탐색으로 가능하다고 생각을 하였다.

 

따라서 비교하는 문자 a, b에 대해서 알파벳 배열을 만들었으며 a와 b의 문자가 다를경우 각각의 문자를 서로 다르게 변경해주었으며

만약 이미 변경했고 b의 문자와 다를 경우 이는 비슷한 단어가 아니기 때문에 개수를 추가하지 않는다.

 

정답 코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    int y;
    int r;
};

int dx[] = {0 ,0, -1, 0, 1, 1, -1, -1, 1};
int dy[] = {0, -1, 0, 1, 0, -1, 1, -1, 1};
int N, cnt;
string arr[101];

void solve() {
    for(int i = 0; i < N; i++) {
        for(int j = i+1; j < N; j++) {
            string a = arr[i];
            string b = arr[j];

            char visited1[26] = {0};
            char visited2[26] = {0};
            bool flag = false;

            for(int k = 0; k < a.size(); k++) {
                int idx1 = a[k] - 'a';
                int idx2 = b[k] - 'a';

                if(visited1[idx1] == 0 && visited2[idx2] == 0) {
                    visited1[idx1] = b[k];
                    visited2[idx2] = a[k];
                }
                else if(visited1[idx1] != b[k] || visited2[idx2] != a[k]) {
                    flag = true;
                    break;
                }
            }

            if(!flag) cnt++;
        }
    }

    cout << cnt;
}

void input() {
    cin >> N;

    for(int i = 0; i < N; i++) {
        cin >> arr[i];
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
    solve();
}