[백준] 1987번 알파벳

백준_1987

올해 초 알고 특강 입과 테스트에서 풀지 못 했던 문제였다
BFS로만 계속 시도했던 것이 문제였다
백트래킹으로 쉽게 풀린 문제였는데 풀지 못 했다는게 너무 아쉬웠다

r, c = map(int, input().split())
board = [list(input()) for _ in range(r)]
answer = []
answer.append(board[0][0])
result = 0

dx = [0,0,1,-1]
dy = [1,-1,0,0]
def dfs(x,y):
    global result
    result = max(result, len(answer))

    for k in range(4):
        nx = x+dx[k]
        ny = y+dy[k]
        if 0<=nx<r and 0<=ny<c:
            if board[nx][ny] not in answer:
                answer.append(board[nx][ny])
                dfs(nx,ny)
                answer.remove(board[nx][ny])

dfs(0,0)
print(result)