https://www.acmicpc.net/problem/1987

---

1. DFS 풀이(PyPy3)

import sys

r, c = map(int, sys.stdin.readline().rstrip().split())
graph = [list(sys.stdin.readline().rstrip()) for _ in range(r)]

ans = [1]

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def dfs(x, y, path, cnt):
    ans[0] = max(ans[0], cnt)

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < r and 0 <= ny < c and graph[nx][ny] not in path:
            path.add(graph[nx][ny])
            dfs(nx, ny, path, cnt + 1)
            path.discard(graph[nx][ny])


dfs(0, 0, set(graph[0][0]), 1)
print(ans[0])

2. BFS 풀이(Python3)

import sys

r, c = map(int, sys.stdin.readline().rstrip().split())
board = [list(sys.stdin.readline().strip()) for i in range(r)]
max_count = 1

def bfs():
    global max_count
    queue = set([(0, 0, board[0][0])])
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]

    while queue:
        x, y, route = queue.pop()
        for i in range(4):
            a, b = x + dx[i], y + dy[i]
            if (0 <= a < r) and (0 <= b < c) and board[a][b] not in route:
                queue.add((a, b, route + board[a][b]))
                max_count = max(max_count, len(route) + 1)

bfs()
print(max_count)

3. 후기

set자료형을 사용하지 않고 list를 사용할 경우 시간초과 발생.