[백준] 1987(파이썬) - 알파벳

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

1987번: 알파벳

• 이 문제는 보고 이 문제야말로 DFS를 이용하는 문제다 라고 생각했다. 근데 생각해보니까 BFS로도 풀 수 있다ㅎㅎ
• 여기서 중요한점은 맨 처음에 리스트를 하나만들어서 알파벳이 사용됐을 경우 리스트에 넣어서 만약에 DFS함수안에서 다음 탐색 x,y좌표에 리스트에 있는 알파벳이 없을 경우 DFS 재귀를 돌렸는데 이렇게 하니까 시간초과가 발생하였다.
• 생각한 방법은 알파벳을 아스키코드를 이용해서 숫자로 변환해서 26개의 0을 담고 있는 visited 리스트를 만들어준 뒤, 각각의 알파벳을 방문했을 때 그 알파벳에 해당하는 인덱스를 1로 방문 처리 하는 방법을 사용했다. 
• 또 하나 중요했던 점은 DFS 함수안에서 재귀를 사용할 때, 방문처리를 하고 DFS를 돌린 뒤, 방문처리를 해제 해주는 백트래킹 방법을 사용해야 다른 경로로 돌고있는 DFS 재귀함수가 해당 알파벳을 방문할 때 사용할 수 있는 점이다.

# # 이문제야말로 DFS다.
import sys
input = sys.stdin.readline

r,c = map(int,input().split())
graph = [list(map(lambda a : ord(a)-65,input())) for _ in range(r)]
visited = [0]*26

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

def dfs(x,y,cnt):
    global Max
    if Max < cnt:
        Max = cnt
        
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        # 문자열 처리하니까 시간초과가 난다 알파벳개수만 큼 리스트 만들어서
        if 0 <= nx < r and 0 <= ny < c and visited[graph[nx][ny]] == 0:
            visited[graph[nx][ny]] = 1
            dfs(nx,ny,cnt+1)
            visited[graph[nx][ny]] = 0

Max = 1

visited[graph[0][0]] = 1
dfs(0,0,Max)

print(Max)
# import sys
# input = sys.stdin.readline

# r,c = map(int,input().split())
# graph = [list(input().rstrip()) for _ in range(r)]

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

# def dfs(x,y,cnt):
#     global Max
#     if Max < cnt:
#         Max = cnt
#   #  alphabet.append(graph[x][y])

#     for i in range(4):
#         nx = x + dx[i]
#         ny = y + dy[i]
#         # 문자열 처리하니까 시간초과가 난다 알파벳개수만 큼 리스트 만들어서
#         if 0<= nx < r and 0<= ny < c and graph[nx][ny] not in alphabet:
#             alphabet.append(graph[nx][ny])
#             dfs(nx,ny,cnt+1)
#             alphabet.remove(graph[nx][ny])
# Max = 1

# alphabet = []
# alphabet.append(graph[0][0])
# dfs(0,0,Max)
# print(Max)
# 이문제야말로 DFS다.