[BOJ] 백준 1987. 알파벳 - DFS, 백트래킹

🥇 알파벳

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

💡 아이디어

처음엔 BFS로 접근해서 풀이했는데,

최대한 깊게! 어디까지 갈 수 있는지를 보는 것이어서 DFS로 바꿨다.

즉 가능한 모든 경로를 탐색하는 문제다. → DFS로 이동가능한 경로를 탐색하고, Backtracking으로 모든! 경로를 확인한다

🧑🏻‍💻 풀이

⏰ 시간초과코드: set() 사용

#알파벳 골

r, c = map(int, input().split())
arr = [list(input().rstrip()) for _ in range(r)]
ans = 0
alp = set()

dx = [1,-1,0,0]
dy = [0,0,1,-1]

def dfs(x, y, count):
    global ans
    ans = max(ans, count)
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<=nx<r and 0<=ny<c and not arr[nx][ny] in alp:
            alp.add(arr[nx][ny])
            dfs(nx, ny, count+1)
            alp.remove(arr[nx][ny]) #가장최근 알파벳을 지워줘야함!

alp.add(arr[0][0])
dfs(0,0,1)
print(ans)

✅ 통과 코드: ord 사용

#알파벳 골
r, c = map(int, input().split())
arr = [list(input().rstrip()) for _ in range(r)]
ans = 0
visited=[0]*26 #알파벳은 총 26개

dx = [1,-1,0,0]
dy = [0,0,1,-1]

def dfs(x, y, count):
    global ans
    ans = max(ans, count)
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<=nx<r and 0<=ny<c and visited[ord(arr[nx][ny])-ord('A')]==0:
            visited[ord(arr[nx][ny]) - ord('A')] = 1
            dfs(nx, ny, count+1)
            visited[ord(arr[nx][ny]) - ord('A')] = 0

visited[ord(arr[0][0]) - ord('A')] = 1
dfs(0,0,1)
print(ans)

⚠️

집합의 경우 in 연산자의 대부분의 경우는 시간복잡도가 O(1)이지만, 최악의 경우 O(n)이 될 수도 있다.

visited 리스트를 활용해서 풀이했는데, 리스트는 항상 O(1)의 시간복잡도를 가진다.

최악의 경우를 고려해서,, visited를 사용하는게 낫다 (GPT 참고)

 

문제 핵심은 DFS를 수행하고, 가장 최근 방문한 알파벳을 삭제하는 것! (백트래킹을 위함) 너무 어려움.

이를 통해 경로상의 알파벳이 중복되지 않고, 최대한 많은 알파벳을 방문할 수 있다.