[BOJ/백준] 1987번 알파벳 - Python/파이썬 [해설/풀이]

📌 문제

---

📝 입력

---

💻 출력

---

📖 예제 입출력

---

📌 풀이

---

📖 해설

---

BFS, DFS 응용 문제
queue로 deque 대신 set을 사용하는 응용력 필요
시간초과, 메모리초과 등의 문제로 상당한 응용력을 요구하는 문제

💻 전체코드

---

import sys
input = sys.stdin.readline

def BFS(graph):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    result = 1
    queue = set([(0, 0, graph[0][0])])			# set 중복제거, 시간초과 방지
    while queue:
        x, y, visited = queue.pop()
        result = max(result, len(visited))		# 문자열 길이를 통해 이동거리 측정
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < R and 0 <= ny < C:
                if not graph[nx][ny] in visited:	# 지나온 모든 알파벳과 다르다면
                    queue.add((nx, ny, visited + graph[nx][ny]))
    return result

R, C = map(int, input().split())
board = [input().rstrip() for _ in range(R)]

answer = BFS(board)
print(answer)