Python - [메모제이션 미학습 Backjoon 20166] 문자열 지옥에 빠진 호석

 

해시를 학습하던 중, 해당 문제를 접했습니다.

보자마자 어? 왜 해시지? DFS 문제아닌가?라는 생각이 들었고 DFS로 구현해서 제출하였는데 시간초과가 났네요 ㅎㅎ..

STL을 사용하지 않아서 에러가 났나 싶어, C언어로도 구현을 했으나, 알고보니 메모제이션을 해시로 구현해서 시간 단축을 시키면 되었습니다.

즉, DFS로 전체 알고리즘 설계 -> 시간 단축을 위해 메모제이션(해시) 적용 이 필요한 문제 였네요.

 

아직 메모제이션에 대해 완벽 숙지가 안되서 실패 카테고리에 남겨놓고, DFS만 구현된 코드 업로드 합니다.

 

+ DFS 문제라고 빠르게 판단할 수 있던 이유는 비슷한 유형의 문제를 이미 많이 접해서 바로 생각이 났습니다. 유사 문제 링크 남깁니다.

2025.01.03 - [Computer Science/알고리즘 문제] - C - [백준 1987] 알파벳 (feat. 백트래킹, DFS & 최장거리 탐색)

C - [백준 1987] 알파벳 (feat. 백트래킹, DFS & 최장거리 탐색)

 

 

코드

 

 

import sys

# 깊이 우선 탐색 함수 정의
def dfs(x, y, k, count):
    # 방문 처리는 필요 없으므로 제거
    count += 1

    # 문자열을 모두 탐색한 경우
    if count == len(k):
        return 1

    result = 0
    for i in range(8):
        # 방향 이동 후 좌표 조정 (토러스 형태)
        nx = (x + dx[i] + N) % N  # 양수 변환
        ny = (y + dy[i] + M) % M  # 양수 변환

        # 조건 검사 및 탐색 진행
        if grid[nx][ny] == k[count]:
            result += dfs(nx, ny, k, count)

    return result

# 입력 처리
input = sys.stdin.readline

# 입력값 받기
N, M, K = map(int, input().split())

# 방향 벡터 정의 (상, 하, 좌, 우, 대각선 4방향)
dx = [0, 0, -1, 1, -1, 1, -1, 1]
dy = [-1, 1, 0, 0, 1, -1, -1, 1]

# 격자판 정보 입력
grid = [input().strip() for _ in range(N)]

# 문자열 탐색 및 결과 출력
for _ in range(K):
    word = input().strip()
    result = 0

    # 모든 위치에서 탐색 시작
    for i in range(N):
        for j in range(M):
            if grid[i][j] == word[0]:  # 시작 문자가 일치할 때만 탐색
                result += dfs(i, j, word, 0)

    print(result)