백준[ 1987 | Python ] 알파벳

문제

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

풀이

주어진 알파벳판 위에서 (0,0)칸을 시작으로 DFS 탐색을 수행한다.
이 때 주어진 조건 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 카넹 적혀있는 알파벳과는 달라야 한다.
를 고려하여 조건이 맞는 모든 발판을 방문하고 가장 이동이 길었던 결과를 출력한다.

r, c = map(int,input().split())
board = []
for _ in range(r):
    board.append(list(input()))

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

# v =[]
# def dfs(s):
#     global res
#     res = max(res,len(v)+1)
#     x,y = s[0],s[1]
#     for i in range(4):
#         nx,ny = x+dx[i],y+dy[i]
#         if 0<=nx<r and 0<=ny<c and not board[nx][ny] in v:     
#             v.append(board[nx][ny])
#             dfs((nx,ny))
#             v.pop()
# dfs((0,0))
# print(res)

def dfs_stack(s):
    global res
    stack = set()
    stack.add((s[0],s[1],board[0][0]))
    
    while stack:
        row,col,v = stack.pop()
        for i in range(4):
            nx,ny = row+dy[i], col+dx[i]
            if 0<=nx<r and 0<ny<c and board[nx][ny] not in v:
                stack.add((nx,ny,board[nx][ny]+v))#v는 실제로 변하지 않았다 ?
                res = max(res, len(v)+1)
    return res
print(dfs_stack((0, 0)))

생각 & 정리

처음 재귀로 구현한 코드는 시간초과로 인해 해결되지 못했다.
이후로 재귀가 아닌 stack을 통해 구현을 했는데, pypy에서는 해결되었지만 python에서는 해결되지 않았다.
이는 stack을 set으로 설정하여 해결 가능했다.

몇가지 의문점이 들었다.
첫번째는 line10에서 board[nx][ny]를 리스트로 만든 v에 append를 시도하면 제대로 동작되지 않았는데 이는 v에 현재 밟은 발판을 추가하면 다음 다른 방향을 탐색할 때 변경된 v를 기준으로 탐색하기 때문이었다.
따라서 이를 리스트 타입으로 +를 사용하거나 문자열에 더해주는 방법으로 해결할 수 있었다.

다른 의문점은 set을 통해서 경과시간이 줄어든 점이었다.
중복을 허용하지 않고 순서를 보장하지 않는 특성을 통해서 현재까지 밟은 발판과 현재 탐색할 발판을 중복으로 탐색하지 않게끔처리 했기 때문인 것 같다.