[백준 1987] 알파벳 (python)

 

풀이

BFS로 풀게 되면 알파벳을 한번씩 방문하는 조건을 체크할 수 없다. 

따라서 하나씩 가능성을 탐색하는 DFS로 풀어야 한다.  

 

재귀를 이용하여 DFS를 구현하였다. 

 

이미 방문한 적 있는 알파벳을 list에 append하여 저장하고 

in 연산자를 사용하여 방문한적 있는지를 확인했더니 시간 초과가 났다.

 

그래서 알파벳을 길이가 26인 배열로 표현하여 포함 여부를 체크했더니 성공할 수 있었다. 

 

 python에서는 문자를 아스키 코드에 해당하는 정수로 변환하기 위해 아래와 같이 ord 라는 연산자를 사용한다. 

ord('A') 

ord(board[new_x][new_y])

 

# 알파벳 
# 세로: R, 가로: C
# 행 : x , 열 : y 

dx =[1, 0, -1, 0]
dy =[0, 1, 0, -1]
R, C = map(int, input().split(" "))

board = []
alpha = [0] * 26
visited =[[0]*C for _ in range(R) ]

for i in range(R):
  el = list(input())
  board.append(el)

ans =1
def dfs(now, visited, alpha ,cnt):
  global ans 
  visited[now[0]][now[1]] = 1
  alpha[ord(board[now[0]][now[1]]) - 65 ] =1
  for i in range(4):
    new_x = now[0] + dx[i]
    new_y = now[1] + dy[i]
    if 0  <= new_y < C  and 0 <= new_x < R  and visited[new_x][new_y] ==0:
      if alpha[ ord(board[new_x][new_y]) - 65] == 1:
        continue
      if cnt+1 > ans :
        ans = cnt+1
      dfs([new_x, new_y], visited, alpha ,cnt+1)
      visited[new_x][new_y] = 0
      alpha[ ord(board[new_x][new_y]) - 65] =0
  return 
dfs([0,0], visited, alpha ,1)
print(ans)