백준 15705 단어 찾기

N*M 배열에 단어 S 있으면 1 반환 없으면 0 반환

브루트 포스 방식, 완전 탐색

python 풀이

import sys

def Input_Data():
    readl = sys.stdin.readline
    word = str(readl().split()[0])
    N, M = map(int, readl().split())
    word_map = [[i for i in str(readl().split()[0])] for _ in range(N)]
    return word, N, M, word_map


def chk_word(r, c):
    for dy, dx in d:
        idx = 0
        if word_map[r][c] == word[idx]:
            nr, nc = r+dy, c+dx
            idx += 1
            while 0 <= nr < N and 0 <= nc < M and idx < len(word) and word_map[nr][nc] == word[idx]:
                nr, nc = nr+dy, nc+dx
                idx += 1
            if idx == len(word):
                return 1
    return 0

def sol():
    for r in range(N):
        for c in range(M):
            if chk_word(r, c):
                return 1
    return 0

word, N, M, word_map = Input_Data()
d = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]
print(sol())