• 출처 : https://www.acmicpc.net/problem/16236

• 알고리즘 : DFS, 재귀

• DFS 구현 방법

  • 현재 좌표에서 경로 길이 update
    • 26일 경우 종료
  • 상, 하, 좌, 우로 재귀
    • visited = True, 재귀, visited = False

• visited 구현 방법

  • A-Z를 ord 함수로 0-25로 바꾼 뒤 boolean 저장
  • set 안됨 (why??)

• 소감

  • 구글링 소스 코드 참고
  • pypy3 통과
  • 시간 제한이 굉장히 빡센 것 같다
  • 상, 하, 좌, 우로 반복할 때도 함수로 if문 쓰니 통과했다가 다시 하니까 시간 초과 됨
  • (1,-1,0,0 ) (0,0,1,-1) 하니까 됨
  • visited를 set으로 만들어서 add, remove 했을 때 왜 안되는 건지 모르겠다 복잡도 O(1) 인데..
  • 전역 변수를 더 많이 활용해야겠다

코드

def get_new_pos(pos, d):
    if d == 'u':
        return (pos[0]+1, pos[1])
    if d == 'd':
        return (pos[0]-1, pos[1])
    if d == 'l':
        return (pos[0], pos[1]-1)
    if d == 'r':
        return (pos[0], pos[1]+1)


def out(pos):
    if 0 <= pos[0] < len(board):
        if 0 <= pos[1] < len(board[0]):
            return False
    return True


def get_ord(pos):
    word = board[pos[0]][pos[1]]
    return ord(word) - ord('A')


def dfs(curr_pos, count):

    di = [1,-1,0,0]
    dj = [0,0,1,-1]

    global max_length

    if count == 26:
        max_length = 26
        return

    max_length = max(max_length, count)

    # for d in ['u','d','l','r']:
    for d in range(4):

        # new_pos = get_new_pos(curr_pos, d)
        new_pos = (curr_pos[0]+di[d], curr_pos[1]+dj[d])

        if out(new_pos):
            continue
        if visited[get_ord(new_pos)]:
        # if board[new_pos[0]][new_pos[1]] in visited:
            continue

        # visited.add(board[new_pos[0]][new_pos[1]])
        visited[get_ord(new_pos)] = True
        dfs(new_pos, count+1)
        visited[get_ord(new_pos)] = False
        # visited.remove(board[new_pos[0]][new_pos[1]])



def init():
    n, m = map(int, input('').split(' '))
    board = [list(input('')) for i in range(n)]
    return n, m, board


n, m, board = init()

visited = [False] * 26
visited[get_ord((0,0))] = True
# visited = set()
# visited.add(board[0][0])

max_length = float('-inf')

start = (0,0)

dfs(start, 1)

print(max_length)