[백준]1987 알파벳

1. 풀이

원래 맞았던 문제가 재채점 된 이후 시간초과가 났다. (소스코드1)

dfs로 탐색하며 파라미터로 위치와 현재까지의 word를 저장했다. 이후 새롭게 탐색하는 격자의 알파벳이 word에 있는 알파뱃이면 그자리에서 탐색을 종료했다.

풀이는 똑같지만 시간초과를 줄이기 위해 두가지를 바꿔주었다. (소스코드2)

(1) 격자의 알파벳이 word에 있는지 확인해 주기 위해 (alpabet in word)를 사용했다. 하지만 이러면 word를 한바퀴 다돌아야 하기 때문에 시간이 오래걸린다. 알파벳은 총 26개이므로, 알파벳의 아스키코드를 인덱스로 하는 길이 26의 visited 리스트를 관리하여 특정 알파벳이 현재까지의 단어에 포함되어있는지를 즉시 알 수있도록 해주었다.

※ 이런류의 탐색에서 시간초과를 많이 겪어보았다. 전체 경우의 수의 크기(위 문제에선 26)를 보고 visited로 관리하는 법에 좀 익숙해지자.

(2) 길이가 26이 되면 가질 수 있는 가장 큰 값을 가진것이 된다. (알파벳은 총 26개이므로) 따라서 이때 즉시 종료해주었다.

​

※스택을 활용하면 시간을 더 줄일 수 있을 것 같다..

​

2. 소스코드

(1) 시간초과

dR=[0,0,-1,1]
dC=[1,-1,0,0]

R,C=map(int,input().split())
L=[]
for i in range(R):
    L.append(list(input()))

ans=0
def dfs(i,j,word):
    #print(i,j,word)
    global ans
    for k in range(4):
        tempR=i+dR[k]
        tempC=j+dC[k]
        if 0<=tempR<R and 0<=tempC<C:
            size=len(word)
            #알파뱃 중복되면 종료
            if L[tempR][tempC] in word:
                if ans<size:
                    ans=size
                continue
            else:
                dfs(tempR,tempC,word+L[tempR][tempC])

dfs(0,0,L[0][0])
print(ans)

 

(2) 통과

import sys

dR=[0,0,-1,1]
dC=[1,-1,0,0]

R,C=map(int,input().split())
L=[]
for i in range(R):
    L.append(list(input()))
visited=[0 for i in range(26)]
visited[ord(L[0][0])-65]=1
ans=0
def dfs(i,j,cnt):
    global ans
    for k in range(4):
        tempR=i+dR[k]
        tempC=j+dC[k]
        if 0<=tempR<R and 0<=tempC<C:
            #알파뱃 중복되면 종료
            num=ord(L[tempR][tempC])-65
            if visited[num]:
                if ans<cnt:
                    ans=cnt
                continue
            else:
                visited[num]=1
                if cnt==25:
                    print(26)
                    sys.exit()
                else:
                    dfs(tempR,tempC,cnt+1)
                visited[num]=0

dfs(0,0,1)
print(ans)