[BOJ][Python]1987 풀이

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

1987번: 알파벳

import sys
ssr = sys.stdin.readline

def dfs_stack():
    global ans
    s = [(0, 0, board[0][0])]
    while s:
        r, c, path = s.pop()
        if len(path) > ans:
            ans = len(path)
        if len(path) == 26:
            break
        for dr, dc, in dpos:
            if 0 <= r+dr < R and 0 <= c+dc < C and board[r+dr][c+dc] not in path:
                s.append((r+dr, c+dc, path+board[r+dr][c+dc]))
        
R, C = map(int, ssr().split())
board = [ssr().rstrip() for _ in range(R)]
dpos = [(1, 0), (-1, 0), (0, 1), (0, -1)]
ans = 0
dfs_stack()
print(ans)

독특한 문제였습니다. 일반적인 dfs로도 풀리기는 하는데 서버 상태에 따라 통과를 하기도 하고 통과를 못하기도 해서 다른 풀이를 좀 찾아보다가 대부분의 사람들이 재귀가 아닌 반복문으로 dfs를 푸는 방법을 선택하셨길래 저도 stack을 사용해서 풀어봤는데 런타임이 재귀에 비해 절반 정도로 줄어들어서 괜찮겠다 싶어서 해당 풀이를 올려보겠습니다. 아스키코드로 변환하고 비트연산을 하면서 런타임을 더 줄이는 방법도 있는 것 같은데 제가 그 코드를 완벽하게 이해하진 못해서 일단은 보류하고 왜 재귀를 이용한 풀이와 반복문을 이용한 풀이에서 런타임 차이가 나는지 설명을 드리고자 합니다.

 

일단 코드 설명부터 드리자면, 그래프 탐색 알고리즘을 사용합니다만 문제의 특성상 저는 bfs로 푸는 방법을 생각하진 못했고 dfs로 푸는 것이 훨씬 수월하기 때문에 dfs로 진행을 했습니다. 방문처리 또한 갔던 곳을 또 못가도록 처리를 하는 것이 아니라 같은 알파벳이 나와도 못가기 때문에 어떻게 하면 이미 봤던 알파벳이라고 처리를 할지가 핵심이 아닌가 싶습니다. 저 같은 경우는 처음에는 딕셔너리로 만들어서 재귀 함수가 종료되면 다시 미방문으로 만드는 방법을 이용했었는데 아예 경로를 저장해서 현재 위치의 알파벳이 포함이 되는지 안되는지를 in 메서드로 비교하는 코드가 있어서 해당 내용을 차용해봤습니다.

 

그리고 재귀 함수와 스택 자료형을 이용해서 반복문으로 푸는 코드의 런타임이 차이나는 이유는 오버헤드의 양 때문이라고 합니다. 오버헤드는 프로그램이 실행될 때 추가적으로 발생하는 자원의 소비나 처리 시간을 말하는데 함수를 호출하게 될 경우 매개 변수를 넘겨주거나 복귀할 주소를 저장하거나 지역변수의 생성 및 소멸 등의 작업 즉, 오버헤드가 발생을 하게 됩니다. 따라서 재귀 함수의 경우 이런 그래프 탐색 문제에서 좌표를 이동할 때 마다 호출이 되게 되는데 이 문제처럼 최장 경로를 찾기 위해서는 방문했던 위치를 다시 가지않는 경우의 탐색 문제에 비해서 훨씬 많은 함수 호출이 일어나게 되고 이런 면에서 많은 오버헤드가 발생하는 것입니다. 따라서 함수 호출을 굳이 여러 번 하지 않는 스택을 이용한 반복문을 통한 dfs가 오버헤드를 적게 일으켜 상대적으로 런타임에서 이득을 볼 수 있는 것이죠.

 

사실 이 문제가 아니었다면 그냥 머리로만 당연히 그렇겠지 하고 넘어갈 수 있었던 부분을 직접 구현 방법을 바꿔보면서 런타임을 확인하니까 훨씬 더 와닿는 내용이었습니다. 즐거웠네요.