6.2 예제 : 보글 게임(Python)

 

문제 출처 : algospot.com :: BOGGLE

algospot.com :: BOGGLE

 

---

1. 내가 생각한 풀이 방법

board = [['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']]
visited = [[0] * 5 for _ in range(5)]

# 좌상, 상, 우상, 우, 우하, 하, 좌하, 좌
dr = [-1, -1, -1, 0, 1, 1, 1, 0]
dc = [-1, 0, 1, 1, 1, 0, -1, -1]

def hasWord(r, c, word):
    if len(word) == 1:
        return True
    if board[r][c] == word[0]:
        visited[r][c] = 1
        for i in range(8):
            nr = r + dr[i]
            nc = c + dc[i]
            if nr >= 0 and nr < 5 and nc >= 0 and nc < 5:
                if board[nr][nc] == word[1] and visited[nr][nc] == 0:
                    return hasWord(nr, nc, word[1:])
    else:
        for i in range(8):
            nr = r + dr[i]
            nc = c + dc[i]
            if nr >= 0 and nr < 5 and nc >= 0 and nc < 5:
                return hasWord(nr, nc, word)
    return False
print(hasWord(0, 0, 'PRETTY'))

 

2. 틀린 이유

(1) 기저 사례를 올바르게 정의하지 못함

• 나는 남은 단어의 길이가 1인 경우만 기저 사례로 생각했다.

(2) 재귀 호출의 각 단계에서 반환하는 방법을 잘 못 지정함

• 반드시 return으로 재귀 함수를 호출하는 방법만 있는 것이 아니다.

 

---

3. 해설 풀이 방법

def hasWord(r, c, word):
    # 기저 사례 1: 시작 위치가 범위 밖이면 실패
    if r < 0 or r >= 5 or c < 0 or c >= 5:
        return False

    # 기저 사례 2 : 첫 글자가 일치하지 않으면 실패
    if board[r][c] != word[0]:
        return False

    # 기저 사례 3 : 남은 단어의 수가 1이면 성공
    if len(word) == 1:
        return True

    # 인접한 8칸 검사
    for i in range(8):
        nr = r + dr[i]
        nc = c + dc[i]

        if nr >= 0 and nr < 5 and nc >= 0 and nc < 5:
            if hasWord(nr, nc, word[1:]):
                return True

    return False

4. 해설

(1) 기저 사례는 총 3가지

• 첫 번째, 탐색 시작 위치가 2차원 리스트의 범위 밖이면 False 반환
• 두 번째, 단어의 첫 글자와 2차원 리스트에서 가리키는 첫 글자가 일치하지 않으면 False 반환
• 세 번째, 남은 단어의 수가 1인 경우 True 반환

(2) 2차원 리스트에서 특정 위치에서 인접한 8칸(좌상, 상, 우상, 우, 우하, 하, 좌하, 좌)을 검사

• 인접한 8개의 다른 단어들에 대해서 재귀적으로 함수 반복
• 재귀적으로 함수를 반복 할때는 단어에서 현재 인덱스의 글자를 제외한 다음 인덱스부터의 단어를 검사함

5. 내가 생각한 풀이와 다른 점

(1) 기저 사례

• 나는 기저 사례를 1가지만 생각했지만, 정답은 3개의 기저 사례를 염두해두고 있었다.

(2) 방문 여부 저장

• 나는 방문 여부를 저장하는 또 다른 2차원 리스트를 생성해서 탐색 했지만, 오히려 필요 없었고 옳은 방법도 아니었다.

6. 시간 복잡도 분석

• 단어의 길이가 N일 때, 탐색은 N-1번 진행한다.
• 각 칸에는 최대 8개의 인접한 알파벳이 존재한다.
• 따라서, 검사하는 후보의 수는 8^(N-1) 번
• Big-O 표기법에 따라, O(8^N)

---

7. 후기

  아직 문제를 보고 직감으로 해결하려고 하거나 아무런 생각없이 한 줄 한 줄 적으며 그때 상황에 따라 문제를 해결하려는 경향이 많이 남아있음을 느꼈다. 책의 초장에 나와있는 단계들(문제를 정확히 이해하고, 계획을 세우고, 검증하고 코드를 작성하는 단계 등)을 몸에 익히는 연습이 더 필요함을 느낄 수 있었다.

  특히, 문제를 대충 이해하고 넘어가거나 재귀 함수의 기저 사례를 너무 섣부르게 생각하고 결정하여 코드를 작성하다보니 결과적으로 문제를 푸는데 실패한 꼴을 보이고 말았다.

 

github : Algorithmic_Problem_Soving_Strategies/ex1.py at main · LeeSeok-Jun/Algorithmic_Problem_Soving_Strategies (github.com)

LeeSeok-Jun/Algorithmic_Problem_Soving_Strategies