[백준] 1987번: 알파벳

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

initial

I kinda have been blindly memorising Backtracking template where if we meet the end recursion condition, we return to prevent the main logic from running. For example if we meet a certain depth, we return out.

But here, we cannot do that because we dont know until what depth we need to stop. We dont know the explicit number. So I tried making the condition like this but I get keyerror (tbc) idk why

The simpler and correct approach is not to place a return for this backtracking problem. The main loop will keep running and marking the longest length and it will eventually come to a stop when all the possible 4 moves have been dfs traversed.

I have set the condition like if we meet a character that we have already stored in our set and if current position is not 0,0 then we mark the longest length and return. But I get keyerror

n, m = map(int, input().split())
graph = []
for _ in range(n):
    graph.append(list(input().rstrip()))
ans = 0
moves = [[1, 0], [-1, 0], [0, 1], [0, -1]]
visited = [[False for _ in range(m)] for _ in range(n)]


def dfs(check, row, col):
    global ans
    if row != 0 and col != 0:
        if graph[row][col] in check:
            ans = max(ans, len(check))
            return
    for move in moves:
        next_row, next_col = move[0] + row, move[1] + col
        if 0 <= next_row < n and 0 <= next_col < m:
            if not visited[next_row][next_col]:
                check.add(graph[next_row][next_col])
                visited[next_row][next_col] = True
                dfs(check, next_row, next_col)
                visited[next_row][next_col] = False
                check.remove(graph[next_row][next_col])


visited[0][0] = True
check = set()
check.add(graph[0][0])
dfs(check, 0, 0)
print(ans)

solution

this is weird cuz i need to submit via pypy3

using set

even with py3, i get runtime but the solution is correct. Instead of my way, you should not place a return as mentioned earlier.

and u dont need visited list cuz set() is serving that purpose

import sys
input = sys.stdin.readline

n,m=map(int,input().split())
graph=[]
for _ in range(n):
    graph.append(list(input().rstrip()))
ans=0
moves= [[1,0],[-1,0],[0,1],[0,-1]]
def dfs(count, row,col):
    global ans
    ans=max(ans,count)
    for move in moves:
        next_row,next_col=move[0]+row,move[1]+col
        if 0<=next_row<n and 0<=next_col<m:
            if graph[next_row][next_col] not in check:
                check.add(graph[next_row][next_col])
                dfs(count+1,next_row,next_col)
                check.remove(graph[next_row][next_col])
check = set()
check.add(graph[0][0])
dfs(1,0,0)
print(ans)

using ord()

so the ascii value of A is 65. WE mark visited list of 26 alphabets so size of 26 and we mark each character as visited by converting it to ascii value via ord() and subtracting that value with ascii value of 'A'.

this works with pypy3 b

import sys
input = sys.stdin.readline

n,m=map(int,input().split())
graph=[]
for _ in range(n):
    graph.append(list(input().rstrip()))
ans=0
moves= [[1,0],[-1,0],[0,1],[0,-1]]
visited = [False for x in range(26)]
visited[ord(graph[0][0])-ord('A')]=True
def dfs(count, row,col):
    global ans
    ans=max(ans,count)
    for move in moves:
        next_row,next_col=move[0]+row,move[1]+col
        if 0<=next_row<n and 0<=next_col<m:
            if not visited[ord(graph[next_row][next_col]) - ord('A')]:
                visited[ord(graph[next_row][next_col]) - ord('A')] = True
                dfs(count+1,next_row,next_col)
                visited[ord(graph[next_row][next_col]) - ord('A')] = False
dfs(1,0,0)
print(ans)

complexity

it is conducting 4 dfs searches so since there are 4 choices, it is 4 ^ (nm).
Time Complexity:

• The time complexity of the depth-first search (DFS) algorithm is O(4^(n*m)), where n is the number of rows and m is the number of columns in the graph.
• This is because, in the worst case, the DFS explores all possible paths in the graph.

Space Complexity:

• The space complexity is O(26) for the visited array, which represents whether a letter has been visited or not.
• The additional space used by the recursive call stack for DFS contributes to the overall space complexity, and it is O(n*m) in the worst case.