[백준/2848] 알고스팟어 (Python)

Problem : https://www.acmicpc.net/problem/2848

2848번: 알고스팟어

 

Difficulty : Platinum 4

 

Status : Solved

 

Time : 00:52:22

 

---

 

문제 설명

 

 

알고스팟어는 알고스팟 커뮤니티에서 사용하는 언어다. 이 언어는 영어 알파벳을 사용하지만, 영어와 알파벳 순서는 다르다.

알고스팟어의 알파벳 사전 순으로 정렬되어 있는 단어의 목록이 주어졌을 때, 알고스팟어의 알파벳 순서를 구하는 프로그램을 작성하시오.

 

 

입력 및 출력

 

입력

 

첫째 줄에 단어의 개수 N (N ≤ 100)이 주어진다. 다음 N개 줄에는 알고스팟어 단어가 하나씩 주어진다. 단어의 길이는 최대 10이며, 소문자로만 이루어져 있다.

 

출력

 

첫째 줄에 알고스팟어의 알파벳 순서를 출력한다. 만약, 올바른 순서가 없다면 "!"를, 가능한 순서가 두 개 이상이라면 "?"를 출력한다.

 

입력 예시

 

5
ula
uka
klua
kula
al

 

출력 예시

 

luka

 

 

---

 

풀이

 

우선, 다음 두 가지 경우를 생각해 볼 수 있다.

 

• 사전 순으로 정렬되었다는 전제를 지켰는지
• 전제가 지켜졌다는 하에, 알파벳 순서를 정확히 구할 수 있는지

 

첫 번째가 지켜지지 않는 엣지 케이스를 보자.

• aaa - aa는 사전 순 정렬 전제가 부정되어 있다.
• 즉 prefix가 동일할 때('aa', 'aa') 사전 순으로 뒤에 와야 할(길이가 더 긴) 단어가 뒤에 있다면 전제 자체가 무너졌으므로 '!'를 출력해야 한다.

 

두 번째를 보자. 우리는 실제로 인접한 i, i+1번째 단어들만을 검사하면 된다. 각 단어를 검사하여, i번째와 i+1번째가 차이가 나는 지점에서 두 알파벳의 순서가 결정된다.

• adb - acd 가 존재한다면, 처음으로 차이나는 d - c에서 알파벳의 순서가 결정된다.
• 즉 이를 indegree, outdegree로 참조하여 위상 정렬을 적용해 볼 수 있다.
• indegree가 0인 지점들을 모아 위상 정렬을 수행하자. 

 

위상 정렬을 bfs로 수행(khan 알고리즘)할 때, 다음 상황이 등장할 수 있다.

• 올바른 상황 : 모든 알파벳이 한 그래프 내에 존재하고, 진입 depth가 서로 다른 상황이다. 이 경우는 진입 depth에 따라 정렬하여 출력하면 된다.
• 올바른 순서가 없는 상황 : 그래프 내에서 사이클이 발견될 때이다. bfs를 수행하며 이미 방문한 이전 노드에 접근할 수 있을때 사이클이 존재한다고 볼 수 있다.
• 가능한 순서가 두 개 이상인 상황 : 진입 depth가 동일한 알파벳이 두 개 이상 존재한다면, 그 알파벳들의 순서를 가릴 수 없다. 마찬가지로 그래프가 2개 이상인 상황 역시 동일하다.

 

 

풀이 코드

from collections import deque
import sys
input = sys.stdin.readline

N = int(input())
words = [input().strip() for _ in range(N)]
word_set = set(''.join(words))
wlen = len(word_set)
next_s = { key : [] for key in word_set }
required = { key : 0 for key in word_set }
visited = { key : -1 for key in word_set }
w_visited = set([words[0]])
q = deque()

enable = True
sortable = True
ans = ''

for i in range(N-1) :
  a, b = words[i], words[i+1]
  if a == b :
    continue
  if b in w_visited :
    enable = False
    break
  w_visited.add(b)
  length = min(len(a), len(b))
  flg = False
  for j in range(length) :
    if a[j] != b[j] :
      flg = True
      break
  if not flg :
    if len(a) > len(b) :
      enable = False
      break
    continue
  required[b[j]] += 1
  next_s[a[j]].append(b[j])

for w in word_set :
  if not required[w] :
    visited[w] = 0
    q.append((w, 0))

while q and enable :
  w, d = q.popleft()
  for next_w in next_s[w] :
    if visited[next_w] > -1 :
      enable = False
      break
    required[next_w] -= 1
    if not required[next_w] :
      visited[next_w] = d+1
      q.append((next_w, d+1))

if -1 in visited.values() :
  enable = False
if enable :
  visited = sorted(visited.items(), key = lambda x : x[1])
  for i in range(wlen) :
    w, d = visited[i]
    if d != i :
      sortable = False
      break
    ans += w

if not enable :
  print('!')
elif not sortable :
  print('?')
else :
  print(ans)

풀이 완료!