[python] 백준 1987 : 알파벳

문제 링크
https://www.acmicpc.net/problem/1987

접근 1

처음에는 일단 구현부터 해보자는 마음으로 완전탐색을 시도해보았다.

def f(y, x, cnt, visit):
    global max_cnt
    max_cnt = max(max_cnt, cnt)

    for dy, dx in d:
        ny, nx = y + dy, x + dx
        if not in_range(ny, nx):
            continue
        mask = 1 << idx(board[ny][nx])
        if visit & mask:
            continue
        f(ny, nx, cnt + 1, visit | mask)
        
f(0, 0, 1, 1 << idx(board[0][0]))        

여기서 visit은 0부터 2^26 -1 까지의 정수인데, 어떤 알파벳을 사용했는지 비트마스킹 하여 이미 쓴 알파벳을 거르고자 하였다.

당연히 시간초과가 났고, set을 사용해보기도 하였으나 전부 시간초과가 나왔다.

접근 2

다음 링크를 참고하였다.
https://www.acmicpc.net/board/view/72894

나의 코드가 시간초과가 난 이유는, 특정 위치로 갈 때의 알파벳 path의 중복이 일어났기 때문이다. 말로 하니 어려운데, 그림으로 설명하면 쉽다.

이와 같은 경우 E로 가는 경로 3가지가 모두 같은데, 이 세가지 경로 이후 E부터 다시 시작하는 경우에서 같은 경로라고 봐도 무방하다.

• 의문점: E 이후에 다시 돌아오는 느낌으로 경로가 진행된다면?
  --> 상관이 없다. 어차피 저 세 녀석의 경로가 같아 저 사각형 부분으로 절대 들어오는 경우가 없다.

이 부분을 추가하여 문제를 해결할 수 있었다.

정답 코드

import sys

sys.setrecursionlimit(10 ** 8)
input = lambda: sys.stdin.readline().rstrip()
# idx = lambda x: ord(x) - 65
in_range = lambda y, x: 0 <= y < r and 0 <= x < c

d = [(1, 0), (0, 1), (-1, 0), (0, -1)]

r, c = map(int, input().split())
board = [input() for _ in range(r)]
paths = [[set() for _ in range(c)] for _ in range(r)]
max_cnt = 0
has_alp = {}.fromkeys("ABCDEFGHIJKLMNOPQRSTUVWXYZ")


def f(y, x, path: str):
    global max_cnt
    max_cnt = max(max_cnt, len(path))

    for dy, dx in d:
        ny, nx = y + dy, x + dx
        if (
            in_range(ny, nx)
            and not has_alp[board[ny][nx]]  # 다음 알파벳 한번도 쓰인적 없어야함
            and path + board[ny][nx] not in paths[ny][nx]
            # (현재path + 다음 알파벳) 과 같은 경로 존재해선 안됨
        ):
            paths[ny][nx].add(path + board[ny][nx])
            has_alp[board[ny][nx]] = 1
            f(ny, nx, path + board[ny][nx])
            has_alp[board[ny][nx]] = 0


has_alp[board[0][0]] = 1
paths[0][0].add(board[0][0])
f(0, 0, board[0][0])
print(max_cnt)

골드 4 문제였는데도 꽤나 고전했다...
갈 길이 먼 것 같다.