[1987] 알파벳

bfs/dfs 문제이다. (Backtracking)

맨처음 bfs로 접근하니까 메모리초과가 나고

bfs로 접근한다고 가지치기가 가능한가 생각해보니 그렇지도 않은것같아서

dfs로 바꾸어 접근했다.

 

bfs는 최소 경로의 종료조건에서 탐색을 멈출수 있으면 좋은데,

그렇지 않은 경우에는 메모리문제때문에 bfs를 쓰는게 맞다.

 

python3 인터프리터의 경우에는 시간초과가 나서 pypy3 인터프리터로 제출해서 맞췄는데,

이게 정답범위의 시간복잡도라서 정답인건지 아니면 단순히 pypy3이 효율적이라 정답인건지 찝찝한 느낌이 들었다..

'''
1987 - 알파벳
'''

import sys
from collections import deque

def dfs(R, C, graph):
    queue = deque()
    visited = set()
    visited.add(graph[0][0])
    queue.append(tuple([0, 0, visited]))

    delta_y = [-1, 0, 1, 0]
    delta_x = [0, -1, 0, 1]

    result = 0
    while queue:
        py, px, visited = queue.pop()
        # print(py, px, visited)
        result = max(result, len(visited))
        for dy, dx in zip(delta_y, delta_x):
            if R > py + dy >= 0 and C > px + dx >= 0 and graph[py+dy][px+dx] not in visited :
                visited_c = visited.copy()
                visited_c.add(graph[py+dy][px+dx])
                queue.append(tuple([py+dy, px+dx, visited_c]))

    return result

R, C = map(int, sys.stdin.readline().split())
board = [list(sys.stdin.readline().strip()) for _ in range(R)]

result = dfs(R, C, board)
print(f"{result}")