알고스팟 문제 링크: https://www.algospot.com/judge/problem/read/WORDCHAIN
algospot.com :: WORDCHAIN
단어 제한 끝말잇기 문제 정보 문제 끝말잇기는 참가자들이 원을 그리고 앉은 뒤, 시계 방향으로 돌아가면서 단어를 말하는 게임입니다. 이 때 각 사람이 말하는 단어의 첫 글자는 이전 사람이
www.algospot.com
입력된 단어들을 한번씩만 사용하여 끝말잇기를 한다.
모든 단어를 사용하여 게임이 끝날 수 있는 경우 어떤 순서로 단어를 사용해야 하는지 출력하는 문제이다.
만약 모든 단어를 사용하고 게임이 끝나느 경우가 없다면 IMPOSSIBLE를 출력한다.
알파벳 26개를 정점으로 하는 그래프에서 각 단어의 시작 알파벳을 나오는 방향, 끝나는 알파벳을 들어가는 방향으로 하는 간선을 추가한다.
그래프를 생성한 후에 오일러 서킷/트레일을 이용하여 각 간선의 방문순서를 기록한다.
코드 원본: https://github.com/sbl133/JongmanBook/blob/main/28.%20DFS/WORDCHAIN.cpp
GitHub - sbl133/JongmanBook
Contribute to sbl133/JongmanBook development by creating an account on GitHub.
github.com
댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!
reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2
'Algorithm > algospot' 카테고리의 다른 글
| algospot 어린이날 (문제 ID: CHILDRENDAY) c++ (0) | 2021.10.28 |
|---|---|
| algospot Sorting Game(문제 ID: SORTGAME) c++ (0) | 2021.10.27 |
| algospot 고대어 사전 (문제 ID: DICTIONARY) c++ (0) | 2021.10.21 |
| algospot 에디터 전쟁 (문제 ID: EDITORWARS) c++ (0) | 2021.10.18 |
| algospot 삽입 정렬 시간 재기 (문제 ID: MEASURETIME)c++ (0) | 2021.10.15 |