BOJ - 1987

백준 문제 링크
알파벳

❓접근법

1. 중복을 제거하는 것이 가장 우선이므로,
   deque 대신 set을 사용했다.
   answer = 1로 지정한다.
2. 함수 내에서 answer를 전역변수화 해주고,
   큐에 좌표와 그 좌표의 알파벳을 넣는다.
   큐가 비어있을 때까지 원소를 뽑아서,
   4 방향으로 움직인 뒤에 다음 좌표의 알파벳이 현재까지의 리스트에 없으면
   큐에 다음 좌표와 현재까지의 알파벳 + 다음 좌표의 알파벳을 넣는다.
3. answer = max(answer, len(리스트) + 1)로 갱신해준다.
4. 함수를 좌표 0,0 에서 실행시키고, answer를 출력하면 끝!

👌🏻코드

r, c = map(int, input().split())

graph = []
for _ in range(r):
    graph.append(list(input()))
    
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

answer = 1

def bfs(x, y):
    queue = set([(x, y, graph[x][y])]) # 시간 초과를 줄이려면 중복되는 곳은 제거
    global answer
    while queue:
        x, y, temp = queue.pop() # deque가 아니므로 pop
        
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]
            
            if (0 <= nx < r) and (0 <= ny < c) and graph[nx][ny] not in temp:
                queue.add((nx, ny, temp + graph[nx][ny])) # deque가 아니므로 add
                answer = max(answer, len(temp) + 1)
                
bfs(0,0)
print(answer)