[Week 6] DICTIONARY self review - profitjean

[profitjean]

DICTIONARY self review

1. 해결 시도 과정

그래프로 표현하고 위상정렬을 통해 문자들의 순서를 구할 수 있을 것이라 생각했습니다. 또한, b->a->b 처럼 사이클이 형성되는 경우도 고려해줘야겠다고 생각했습니다.

2. 작성한 코드와 설명

T = int(input().rstrip())
for _ in range(T):
    graph = defaultdict(set)
    N = int(input().rstrip())
    words = []
    visited = {}
    for _ in range(N):
        words.append(input().rstrip())
    # 이전 문자열과 비교하면서 다르다면 그래프에 추가시켜주기
    prev = ""
    for word in words:
        for i in range(min(len(prev), len(word))):
            if prev[i] != word[i]:
                graph[prev[i]].add(word[i])
                visited[prev[i]] = None
                visited[word[i]] = None
                break
        prev = word

3. 막힌 점 및 개선 사항

이후 dfs 구현 이후 역방향으로 reverse 시키는 부분을 구현하지 못했습니다