[BOJ 1987] 알파벳(Python)

문제

알파벳

---

문제 해설

BFS 또는 DFS를 활용하는 문제입니다. 처음엔 DFS에 지나온 알파벳을 담고있는 list를 매개변수로 넣어 in으로 계속 체킹했는데 시간 초과가 났습니다.

그래서 알파벳 개수의 크기만큼 list를 하나 만들어 체킹하는 방식으로 바꿔 시간을 줄였는데 또 시간 초과가 났습니다. 결국 pypy3로 제출하면 시간 초과가 해결됩니다.

이 문제는 bfs로 푸는 것이 더 효과적이고, 방문 체크 리스트도 R X C형식의 2차원 리스트가 아닌 알파벳 개수만큼의 1차원 리스트를 추천합니다.

1. (0,0)에서 DFS를 진행합니다.
2. 4방 탐색을 시작하는데, 알파벳을 만나면 ord(알파벳)을 이용해 정수 형태로 변환하고 해당하는 인덱스를 찾아 이미 방문한 알파벳인지 체크합니다.
3. 만약 방문하지 않은 알파벳이면 재귀호출합니다.

---

풀이 코드

import sys

input = sys.stdin.readline
graph = []
answer = 0
r, c = map(int, input().split())
visited = [False] * 26

for _ in range(r):
    graph.append(list(map(str, input().rstrip())))


def dfs(x, y, depth):
    global r, c, answer
    dx = -1, 0, 1, 0
    dy = 0, 1, 0, -1

    answer = max(answer, depth)

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < r and 0 <= ny < c and not visited[ord(graph[nx][ny]) - 65]:
            visited[ord(graph[nx][ny]) - 65] = True
            dfs(nx, ny, depth + 1)
            visited[ord(graph[nx][ny]) - 65] = False


visited[ord(graph[0][0]) - 65] = True
dfs(0, 0, 1)
print(answer)

---