[백준 1987번] 알파벳 (Python3)

import sys
input = sys.stdin.readline

R,C = map(int,input().split())

alpha = []
for i in range(R):
  alpha.append(input().strip())

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

check = [0]*26
check[ord(alpha[0][0])-65] = 1
result = 0
def go(y,x,num):
  global result
  result = max(result,num)
  for i in range(4):
    y1 = y+dy[i]
    x1 = x+dx[i]
    if R>y1>=0 and C>x1>=0:
      if check[ord(alpha[y1][x1])-65]==0:
        check[ord(alpha[y1][x1])-65] = 1
        go(y1,x1,num+1)
        check[ord(alpha[y1][x1])-65] = 0

go(0,0,1)
print(result)

 

기본적인 백트래킹 문제

문제를 보자마자 풀이가 떠올라서 "너무 쉬운데?" 라고 생각했는데 시간초과가 났다...

 

알파벳이 들어있는지를 검사할 때 in함수를 쓴 것이 원인이었다. 그래서 아스키코드를 이용한 check 함수로 바꿔주었다.

하지만 그래도 python3에서는 시간초과가 났다. pypy3로는 통과가 되었다.

 

다른 사람들 풀이를 보니까 특별히 알고리즘이 잘못됐다기 보다는 그냥 파이썬이 파이썬했다고 보는게 맞는것 같았다.

 

 

오늘의 교훈) 파이썬이 어느정도 익숙해지면 C++도 공부하자