[BOJ][python] 1987. 알파벳

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

1987번: 알파벳

---

💡IDEA

DFS와 백트래킹을 사용하는 문제이다.

문제 자체는 쉽게 접근이 가능하지만 시간초과가 자꾸 발생해서 꽤 고생을 했다.

처음에는 방문 배열에 알파벳 자체를 넣었다 뺐다 하는 식으로 했지만 바로 시간초과가 발생했다.

알파벳을 쉽게 인식할 수 있는 방법을 생각해보다가 알파벳을 숫자로 바꾸어주는 ord 함수를 사용해서 알파벳 개수인 26개만큼의 길이의 배열을 만들어서 사용하기로 했다. 알파벳이 대문자이기 때문에 ord로 바꿔준 후 ord('A')값인 65를 빼주는 것을 주의해야 한다.

DFS를 사용해서 백트래킹을 통해서 다음 알파벳을 사용할 때 사용하지 않을 때 반복하며 알파벳 개수를 센다. 더이상 갈 수 있는 곳이 없을 때 최대 알파벳 개수를 갱신한다.

그래도 자꾸 시간초과가 나서 좀 화났는데… 확인해보니 rstrip 함수보다 strip을 사용하면 시간을 줄일 수 있고, dr과 dc 순서도 영향을 미치는 것 같다. 😡

 

📌CODE

import sys
input = sys.stdin.readline

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

dr = [1, -1, 0, 0]
dc = [0, 0, 1, -1]

visited = [0]*26
ans = 0
def dfs(r, c, cnt):
    global ans
    for k in range(4):
        nr = r + dr[k]
        nc = c + dc[k]
        if 0<=nr<R and 0<=nc<C:
            idx = ord(board[nr][nc])-65
            if not visited[idx]:
                visited[idx] = 1
                dfs(nr, nc, cnt+1)
                visited[idx] = 0
    ans = max(ans, cnt)

visited[ord(board[0][0])-65] = 1
dfs(0, 0, 1)
print(ans)