1. 문제 설명

알파벳

2. 문제 분석

로직 자체는 어떤 탐색 알고리즘을 사용해서든 풀 수 있다. 하지만 파이썬은 시간, 메모리 초과 관련해서 주의할 사항이 많은 문제다.

• 원래 큐나 스택을 디큐로 푸는데, 여기에서는 set으로 풀어야 시간초과가 나지 않았다. 또한 pypy에서는 메모리 초과가 나는 코드가 파이썬에서는 구현 가능한데, 이처럼 언어 별로 실행이 잘 되는 코드가 달랐다.

3. 나의 풀이

import sys

r, c = map(int, sys.stdin.readline().rstrip().split())
nodes = [[] for _ in range(r)]
for i in range(r):
    nodes[i] += list(sys.stdin.readline().rstrip())
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

queue = set()
# 디큐를 쓰면 시간 초과가 난다.
queue.add((0, 0, nodes[0][0]))
answer = 1

while queue:
    row, col, visited = queue.pop()

    for x, y in zip(dx, dy):
        next_row, next_col = row + y, col + x

        if next_row < 0 or next_col < 0 or next_row >= r or next_col >= c: continue

        if nodes[next_row][next_col] not in visited:
            queue.add((next_row, next_col, visited + nodes[next_row][next_col]))
            answer = max(answer, len(visited)+1)

print(answer)