[백준 1987번][Python] - 알파벳

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

 

 

 

 

# 풀이과정

1. 각 알파벳별로 방문 여부를 확인하기 위해서 key값으로 알파벳 대문자를 가지는 딕셔너리를 생성
2. 방문한 알파벳을 key값으로 가지는 value는 1로 설정
3. 도착지점의 좌표와 카운트값을 매개변수로해서 재귀함수호출
4. (2)에서 설정한 value를 다시 0으로 설정해 줘서 백트래킹수행
5. 이 과정을 반복하면서, 가장 큰 값을 가진 카운트값을 출력

 

 

[DFS를 이용한 코드 - pypy에서만 성공]

# ex_1987
import sys
R,C = map(int,sys.stdin.readline().split())
board = [list(sys.stdin.readline().rstrip()) for _ in range(R)]
dx = [1,-1,0,0]
dy = [0,0,1,-1]
atoz = list('ABCDEFGHIJKLMNOPQRSTUVWXYZ')
num = [0 for _ in range(26)]
visited = dict(zip(atoz,num))
maxCnt = 0

def sol(x,y,cnt):
    global maxCnt
    maxCnt = max(maxCnt,cnt)
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        if nx >= 0 and nx < R and ny >= 0 and ny < C:
            if visited[board[nx][ny]] == 0:
                visited[board[nx][ny]] = 1
                sol(nx,ny,cnt+1)
                visited[board[nx][ny]] = 0

visited[board[0][0]] = 1
sol(0,0,1)
print(maxCnt)

 

해당 코드로 python으로 제출하였으나, 시간초과가 발생하였으나, pypy로 제출했을 땐 성공하였다.

시간 복잡도를 줄일 수 있는 다른 방법을 생각해 보았고, 다른 코드들도 찾아보았으나, 별 다른 해결책은 없었고, 내가 짠 코드로도 충분하다고 생각한다.