백준: 2186 문자판

문제

2186번: 문자판

 

문제 풀이

 목표가 되는 문자열과 일치하는 경우의 수를 찾는 문제이다. 이를 위해서 `상, 하, 좌, 우`로 K 만큼씩 이동할 수 있다. 문제를 풀기 위해서는 단순히 DFS를 통해 경우의 수를 찾게 되면 시간 초과가 발생한다. 따라서 메모이제이션을 통해 이미 체크한 경우의 수라면 해당 경우의 수를 체크하지 않아야(가지치기) 한다.

 

 처음에는 `dirs = ((0, 1), (0, -1), (-1, 0), (1, 0))`를 사용하여 한 방향씩 체크하도록 하였더니 Python3에서 시간초과가 발생하였다. 다른 사람들의 풀이를 보니, 방향을 접근할 때, `next_x`, `next_y`에 따라 두 가지의 가지로 뻗는 경우로 푸는 것이 더 효율적이라는 것을 알고 코드를 수정하였다.

 

코드

 sys import stdin


def dfs(loc, idx):
    global answer
    x, y = loc
    
    # 가지치기 1: 이미 체크한 경우
    if check[x][y][idx] != -1:
        return check[x][y][idx]
    
    # 가지치기 2: target 문자와 일치하지 않을 경우
    if board[x][y] != target[idx]:
        check[x][y][idx] = 0
        return 0
    
    # 찾는 문자와 일치하는 경우
    if idx == len(target) - 1:
        return 1

    cur_answer = 0
    for k in range(-K, K + 1):
        if not k:
            continue

        next_x, next_y = x + k, y + k

        if 0 <= next_x < N:
            cur_answer += dfs((next_x, y), idx + 1)
        if 0 <= next_y < M:
            cur_answer += dfs((x, next_y), idx + 1)

    check[x][y][idx] = cur_answer

    return check[x][y][idx]


if __name__ == '__main__':
    answer = 0
    N, M, K = map(int, stdin.readline().split())
    board = [stdin.readline().strip() for _ in range(N)]
    target = stdin.readline().strip()

    dirs = ((0, 1), (0, -1), (-1, 0), (1, 0))
    check = [[[-1] * len(target) for _ in range(M)] for _ in range(N)]

    for i in range(N):
        for j in range(M):
            if board[i][j] == target[0]:
                answer += dfs((i, j), 0)

    print(answer)