[Seop's의 코드풀이] 백준 9202 Boggle - Python

www.acmicpc.net/problem/9202

9202번: Boggle

 

 

 

문제 요약

이번 문제는 문제를 파악하는데에도 시간이 다소 걸렸다. 필자처럼 문제를 파악하기 힘드신 분들을 위해 사진으로 표현하면 다음과 같다.

단어목록과 보드가 주어지면 이 안에서 단어목록에 있는 단어들을 찾으면 되는 것이다. 

주어진 보드에서 단어목록에 있는 단어를 모두 찾았다면 그 이후의 정답을 내는 작업은 매우 간단하다. 문제에서 하라는대로 하면 된다. 

 

문제풀이 IDEA

문제를 해결하기 위한 IDEA는 사실 위에 필자가 명시한 그림에 있다. 

단어 목록에서 ICPC라는 단어를 찾으려고 한다면 우린 먼저 알파벳 I 를 찾을것이다.

그다음 주변에 C 가 있는지 확인하고 P, C를 순차적으로 찾아 나설 것이다. 

그렇다면 단어 목록에 있는 단어들 모두를 하나씩 찾아나아가면 될까? 되긴 하겠지만 굉장히 많은 시간이 걸릴것이다. 

이러한 문제를 해결하려 Trie 자료구조를 이용하여 문제를 해결하였다.  Trie 자료구조란?

Trie 자료구조

Trie 자료구조를 통해서 찾아야할 단어 목록을 저장한 다음에 주어진 보드에서 탐색을 진행하는 방식으로 진행했다.  

 

Trie 자료구조를 알고있다면 크게 어렵지 않게 해결 할 수 있으나 필자는 시간이 다소 걸린 문제였다...

본 문제는 코드가 길어 전체 코드는 링크로 대신하겠습니다. 

 

전체코드 보기

miseop25/Back_Jun_Code_Study