[백준]#1987 Python

백준 1987번 알파벳

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

전체코드

import sys
input = sys.stdin.readline


def DFS(array, x, y):
    global visited, length
    visited += array[y][x]

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]   
        if 0 <= nx < C and 0 <= ny < R and array[ny][nx] not in visited:
            DFS(array, nx, ny)

    length = max(len(visited), length)
    visited = visited.strip(visited[-1])
    return


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

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

visited, length = '', 0

DFS(mapp, 0, 0)
print(length)

Pypy3 로 통과,,,

접근법

다른 DFS 문제와 비슷하게 재귀함수를 사용해 상하좌우를 체크해 나갔다.
전형적인 DFS 풀이 방법은 방문, 미방문 처리를 알파벳이 그려진 그래프와 동일한 위치에 체크해 나가는 방식인데, 최대의 문자열 길이를 구해야 했기 때문에 방문 처리를 하나의 문자열로 만들어도 좋겠다고 생각했다.
-> 문자열로 방문 처리를 하면 방문 여부도 알 수 있고, 마지막으로 갱신된 최대 값이 문자열 자체의 길이이기 때문에 새로운 변수를 잡고 연산할 필요가 없음,

다만 아까 말했듯이 방문 여부를 알파벳이 문자열에 있는지 없는지만 확인하고 좌표값으로 확인하지 않기 때문에 중복되는 연산이 존재함(시간초과의 이유인듯)