[python] 1411, 비슷한 단어

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

1411번: 비슷한 단어

 

[문제]

만약 어떤 단어A를 숌스럽게 바꿔서 또다른 단어 B로 만든다면, 그 단어는 비슷한 단어라고 한다.

어떤 단어를 숌스럽게 바꾼다는 말은 단어 A에 등장하는 모든 알파벳을 다른 알파벳으로 바꾼다는 소리다. 그리고, 단어에 등장하는 알파벳의 순서는 바뀌지 않는다. 두 개의 다른 알파벳을 하나의 알파벳으로 바꿀 수 없고, 임의의 알파벳을 자기 자신으로 바꾸는 것은 가능하다.

예를 들어, 단어 abca와 zbxz는 비슷하다. 그 이유는 a를 z로 바꾸고, b는 그대로 b, c를 x로 바꾸면, abca가 zbxz가된다.

단어가 여러 개 주어졌을 때, 몇 개의 쌍이 비슷한지 구하는 프로그램을 작성하시오.

 

[입력]

첫째 줄에 단어의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에 한 줄에 하나씩 단어가 주어진다. 단어의 길이는 최대 50이고, N은 100보다 작거나 같은 자연수이다. 모든 단어의 길이는 같고, 중복되지 않는다. 또, 알파벳 소문자로만 이루어져 있다.

 

[출력]

첫째 줄에 총 몇 개의 쌍이 비슷한지 출력한다.

 

 

[풀이]

n = int(input())
word = []
dic = dict()
cnt = 0

for _ in range(n):
  word.append(input())

word_len = len(word[0])

for i in range(n - 1): # i ~ n-1까지 -> 고정된 비교 대상
  for j in range(i + 1, n): # i+1 ~ n까지 -> i번째 문자열과 비교할 문자열
    dic = dict()
    flag = 1 
      # 반복문이 끝까지 돌아갔는지 확인할 장치
    for k in range(word_len):
       # 문자열을 알파벳 단위로 확인하기 위한 값
      if word[i][k] not in dic.keys(): 
        # i번째 문자열의 k번째 글자가 딕셔너리의 키 안에 없고
        if word[j][k] not in dic.values(): 
          # 두 개의 알파벳이 하나로 변경될 수 없으므로
          # 현재 읽은 알파벳으로 변경된 값이 없을 때 
          dic[word[i][k]] = word[j][k]
            # 딕셔너리에 저장
        else:
          flag = 0
          break;
      else:
        if word[j][k] != dic[word[i][k]]:
          # key 안에는 알파벳이 존재하는데 다른 문자로 변경되었다면
          # 비슷한 문자열이 아니므로 break
          flag = 0
          break;
    if flag == 1:
      # 반복문이 끝까지 돌아갔다면
      cnt += 1
        # 개수 + 1

print(cnt)