DFS, 백트래킹 - 1987번: 알파벳

dfs(maps, nx, ny, alphabets.union({maps[nx][ny]}), level + 1)
이렇게 set.union({원소})로 넘기게 되면 매번 새로운 set을 만들어야 하므로 set 복사비용으로 인해 시간초과 발생함!
-> 그냥 add() 했다가 백트래킹 시 remove()해주는 게 성능 측면에서 더 좋음

r, c = map(int, input().split())
maps = []
for i in range(r):
    line = list(input())
    maps.append(line)

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

alphabets = {maps[0][0]}
max_cnt = 0

def dfs(maps, x, y, alphabets, level):
    global max_cnt

    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        
        if 0 <= nx < r and 0 <= ny < c and maps[nx][ny] not in alphabets:
            a = maps[nx][ny]
            alphabets.add(a)
            
            # dfs(maps, nx, ny, alphabets.union({maps[nx][ny]}), level + 1) 
            # 이렇게 set.union({원소})로 넘기게 되면 매번 새로운 set을 만들어야 하므로 set 복사비용으로 인해 시간초과 발생함 주의 -> 그냥 .add() 했다가 .remove()해주는 게 성능 측면에서 더 좋음
            
            dfs(maps, nx, ny, alphabets, level + 1)
            alphabets.remove(a) # 백트래킹 시 지워주기
            

    
    max_cnt = max(max_cnt, level)

dfs(maps, 0, 0, alphabets, 1)

print(max_cnt)