백준 1987: 알파벳 - 백트래킹, DFS, 비트마스킹 (Python/파이썬)

시간 초과 줄이려고 비트마스킹 쓰고 여러가지 해봤는데 결론은 python3으로는 통과 못하고 pypy 써야만 하는 문제였다. 붙잡고 있던 시간이 아까워

1. dfs + 백트래킹

import sys
input = sys.stdin.readline

r, c = map(int, input().split())
board = list(input().strip() for _ in range(r))

def dfs(row, col, path):
    global max_path
    max_path = max(max_path, path)

    dr = [-1, 1, 0, 0]
    dc = [0, 0, -1, 1]

    for i in range(4):
        nr = row + dr[i]
        nc = col + dc[i]

        if 0 <= nr < r and 0 <= nc < c and not visited[ord(board[nr][nc])-65]:
            visited[ord(board[nr][nc])-65] = 1
            dfs(nr, nc, path + 1)
            visited[ord(board[nr][nc])-65] = 0

    return max_path

max_path = 0
visited = [0] * 26
visited[ord(board[0][0])-65] = 1
print(dfs(0, 0, 1))

2. 경로 탐색 시 비트 마스킹 적용

import sys
input = sys.stdin.readline

r, c = map(int, input().split())
board = [input().strip() for _ in range(r)]

dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]

def dfs(row, col, bitmask, path):
    global max_path
    max_path = max(max_path, path)

    for i in range(4):
        nr = row + dr[i]
        nc = col + dc[i]

        if 0 <= nr < r and 0 <= nc < c:
            idx = ord(board[nr][nc]) - 65
            if not (bitmask & (1 << idx)):  # 방문하지 않은 알파벳이라면
                dfs(nr, nc, bitmask | (1 << idx), path + 1)

max_path = 0
start_char = ord(board[0][0]) - 65
dfs(0, 0, 1 << start_char, 1)
print(max_path)