1.14 1.14

main.py

"""
문제 1.14: 2차원 문자 배열과 단어 문자열이 주어진다. 문자 배열에 인접한 문자의 조합으로,
주어진 단어를 만들 수 있는지 확인해보자.
예를 들어

board = [
  ["A", "B", "C", "E"],
  ["S", "F", "E", "S"],
  ["A", "D", "E", "E"]
]
라는 문자배열와 "ABFE" 라는 문자열이 주어지면, True를 반환하면 된다.

## 제한 사항
- m x n의 크기의 문자 2차원 배열
- 1 <= m <= 200 ~ 300, 1 <= n <= 200 ~ 300
- word의 길이는 1 <= len(word) <= 10^3 ~ 10^4

## 아이디어 (Brute-Force)
1. board 배열의 모든 요소를 순회한다.
2. word[0]과 board[x][y]의 요소가 같다면,
- x, y 위치의 문자와 word의 현재 문자가 같은지를 확인한다.
- x, y가 board 크기를 벗어나는지 확인한다.
- 이미 방문한 위치인지를 확인한다.
- board [x- 1][y]와 word의 다음문자로 재귀 호출
- board [x + 1][y]와 word의 다음문자로 재귀 호출
- board [x][y - 1]와 word의 다음문자로 재귀 호출
- board [x][y + 1]와 word의 다음문자로 재귀 호출
"""
from typing import List


def exist(board: List[List[str]], word: str) -> bool:
    direction = [[-1, 0], [1, 0], [0, -1], [0, 1]]

    def search_direction(x: int, y: int, subword: str):
        if (x < 0 or x >= len(board)) or \
                (y < 0 or y >= len(board[0])):
            return False

        if board[x][y] != subword[0]:
            return False

        if len(subword) == 1:
            return True

        board[x][y] = '.'

        for i, j in direction:
            if search_direction(x + i, y + j, subword[1:]):
                return True

        board[x][y] = subword[0]
        return False

    res = False

    for x in range(len(board)):
        for y in range(len(board[0])):
            if board[x][y] == word[0] and \
                search_direction(x, y, word):
                res = True
                break
    return res


if __name__ == "__main__":
    print(exist([
            ["A", "B", "C", "E"],
            ["S", "F", "E", "S"],
            ["A", "D", "E", "E"]], "ABCE"))