[python] 알고리즘 문제 해결 전략 1권 :: 보글게임 (p150) 문제

예제: 보글 게임 (문제 ID: BOGGLE, 난이도: 하)

문제

5*5 크기의 알파벳 격자를 가지고 하는 게임.

게임의 목적은 상하좌우 / 대각선으로 인접한 칸들의 글자들을 이어서 단어를 찾아내는 것입니다. 각 글자들은 대각선으로도 이어질 수 있으며, 한 글자가 두 번 이상 사용될 수도 있습니다. 주어진 칸에서 시작해서 특정 단어를 찾을 수 있는지 확인하는 문제를 풀어 봅시다.

입력

1

1

PRETTY

출력

True

풀이

1. 간단한 방법 생각

   완전 탐색

2. 문제 분할

   첫 글자 찾기 => 다음 글자를 주변에서 찾기

3. 기저 사례 선택

   더 이상의 탐색 없이 간단히 답을 낼 수 있는 경우

   1. 처음 주어진 위치가 원하는 단어의 첫 글자가 아닌 경우 실패
   2. 1에 해당하지 않고 원하는 단어가 1글자인 경우 성공

   둘의 순서는 바뀌면 안됨

   tip : 입력이 잘못되거나 범위에서 벗어나는 경우, 게임판을 벗어난 경우, 첫 글자가 일치하지 않는 경우도 기저 사례로 택해서 처음에 처리하기

4.1. 구현

   import sys

   # map, direction save
   game_map = [['U','R','L','P','M'],['X','P','R','E','T'],['G','I','A','E','T'],['X','T','N','Z','Y'],['X','O','Q','R','S']]
   side = [[1,0],[1,1],[0,1],[-1,1],[-1,0],[-1,-1],[0,-1],[1,-1]]

   # get input
   try:
       pos_y = int(input())
       pos_x = int(input())
       target_word = input()
   except:
       sys.exit()


   def hasWord(y,x,word):
       if y<0 or y>4 or x<0 or x>4 : # in map?
           return False

       boolean = (word[0]==game_map[y][x])
       word = word[1:] # delete first alphabet

       if boolean:
           if not(len(word)): # word is empty
               return True
           else:
               for case in side: # dynamic programming
                   if hasWord(y+case[0],x+case[1],word):
                       return True
       else:
           return False

   print(hasWord(pos_y,pos_x,target_word))

분석

이전까지는 기저사례라는 개념이 없어서 동적 프로그래밍이나 재귀를 구현할 때도 예외 사항이 생기면 하나씩 추가해가며 구현했었다. 하지만 이렇게 기저사례를 정의해두고 시작하니 더 오류가 적고 빠른 구현이 가능한 거 같다.

그리고 입력을 받을 때는 예외처리를 해두면 편하다. python은 특히 예외처리가 쉬워서 해주는 것이 좋을 것 같다 :>

해당 코드의 알고리즘을 시각화해보면 다음과 같다.

• 시간 복잡도

  최악의 시간복잡도를 계산하면 O(8^(N)) (N: 단어의 길이)

  ex_ A로 가득찬 map에서 AAAAAAH 찾기

  지수 시간 알고리즘임

고찰

책의 예제코드에서는 if문을 차례로 두어서 return문 덕에 else를 따로 구현하지 않고도 논리상 자동적으로 else의 의미가 되도록 했다.

즉, if(조건): return ~ 문장 이후의 문장들은 모두 조건을 만족하지 못한 것들 뿐이다.

하지만 이 방법이 시간적으로 이득이 되는지는 의문이다.