출처: 백준 온라인 저지
https://www.acmicpc.net/problem/1987
처음 풀이 (시간 초과)
DFS 알고리즘으로 구현해 보았다. 기본 BFS/DFS 알고리즘을 크게 벗어나지 않는 문제들과 달리, 확실히 난이도가 높았다. 코드가 정리되지는 않았지만 어쨌든 오랜 시간을 들여 최대 크기(20X20)의 예시들도 빠르게 처리하는 것까지 확인하고 답안을 제출했으나 시간 초과가 떴다.
from sys import stdin, setrecursionlimit
from string import ascii_uppercase
setrecursionlimit(10000)
# 알파벳을 키, 알파벳 번호를 값으로 가지는 딕셔너리
alphabets = dict(zip(list(ascii_uppercase), range(1, 27)))
alpha_check = [0] * 27
def dfs(maps, row, col, check, length):
"""일반적인 DFS 알고리즘과 달리 한번 탐색한 곳은 탐색하지 않는 것이 아니라,
모든 경우의 수를 따져보아야 하므로,
변수의 주소를 할당하는 대신 값을 직접 복사해준다."""
new_check = check.copy()
new_check[alphabets[maps[row][col]]] = 1
aa, bb, cc, dd = 0, 0, 0, 0
if row > 0 and new_check[alphabets[maps[row - 1][col]]] == 0:
aa = dfs(maps, row - 1, col, new_check, length + 1)
if col > 0 and new_check[alphabets[maps[row][col - 1]]] == 0:
bb = dfs(maps, row, col - 1, new_check, length + 1)
if row < (r - 1) and new_check[alphabets[maps[row + 1][col]]] == 0:
cc = dfs(maps, row + 1, col, new_check, length + 1)
if col < (c - 1) and new_check[alphabets[maps[row][col + 1]]] == 0:
dd = dfs(maps, row, col + 1, new_check, length + 1)
return max(aa, bb, cc, dd) + 1
r, c = map(int, stdin.readline().split())
boards = []
for _ in range(r):
boards.append(list(stdin.readline().rstrip()))
print(dfs(boards, 0, 0, alpha_check, 0))
시간을 줄이기 위한 노력들
① 이 문제에서는 숫자가 아니라 알파벳 문자로 노드의 방문 여부를 판단해야 한다. 숫자가 아니므로 인덱스를 통해 접근할 수는 없다. 하지만 아직 돌지 않은 알파벳 전체의 리스트를 매번 확인하기에는 너무 많은 시간이 걸린다. 그래서 위 코드에서는 시간을 절약하기 위해 알파벳 정보를 딕셔너리로 만들어 O(1)로 확인할 수 있게 하였다. 그런데 찾아보니, 파이썬 딕셔너리는 hashmap 기반이고, hash를 계산하는데는 그 만큼의 오버헤드가 든다고 한다.
그래서 어떻게 하면 알파벳 문자를 시간 효율적으로 탐색할 수 있을지를 생각해보았다. 알파벳 문자들을 알파벳 번호로 바꾸어서 인덱스로 접근하면 O(1)로 접근할 수 있었다. 하지만 이렇게 해도 결과는 시간 초과였다.
② 알파벳 문자의 아스키 코드를 기준으로 인덱스로 탐색하는 방법도 마찬가지였다. 그렇다면 DFS 알고리즘 자체의 시간 효율성에 문제가 있다고 생각했다.
③ 재귀 함수로 들어갔다가 나오면 다시 원래대로 check 리스트가 돌아와야 한다. 그래서 내가 구현한 dfs 함수에서는 매번 check 리스트를 복사했는데, 이것이 문제인 것 같았다. 생각해보니 매번 리스트를 복사할 필요 없이, 그저 재귀 함수로 들어갔다가 나올 때, 1로 바꾸었던 값을 다시 0으로 바꾸면 되었다. 드디어 정답이구나 했는데 이번에도 시간 초과가 떴다.
최종 풀이 (파이썬 시간 초과)
from sys import stdin, setrecursionlimit
setrecursionlimit(10000)
def dfs(row, col, check):
check[boards[row][col]] = 1
value = 0
if row > 0 and check[boards[row - 1][col]] == 0:
value = max(value, dfs(row - 1, col, check))
if col > 0 and check[boards[row][col - 1]] == 0:
value = max(value, dfs(row, col - 1, check))
if row < (r - 1) and check[boards[row + 1][col]] == 0:
value = max(value, dfs(row + 1, col, check))
if col < (c - 1) and check[boards[row][col + 1]] == 0:
value = max(value, dfs(row, col + 1, check))
# 재귀에서 빠져나올 때 다시 check를 0으로 해준다.
check[boards[row][col]] = 0
return value + 1
r, c = map(int, stdin.readline().split())
alpha_check = [0] * 26
boards = []
for _ in range(r):
boards.append(list(map(lambda x: ord(x) - 65, \
list(stdin.readline().rstrip()))))
print(dfs(0, 0, alpha_check))
위의 ①, ②, ③을 적용한 코드다. PyPy3으로는 통과했지만, 파이썬으로는 시간 초과가 떴다.
더 이상 할 수 있는 게 없다고 생각하여, 파이썬으로 통과한 코드들을 봤다. 통과한 코드들은 DFS가 아니라 BFS로 구현하고 있었다. 문제 자체는 DFS 문제인데, 파이썬이 속도가 느리다보니 DFS로는 통과하기 어려운 듯하다. BFS로도 구현을 시도해보았으나, 역시나 시간 초과가 떠서 결국 포기했다.
결국 정답 풀이를 구하지는 못했지만, 코드를 수정하는 과정에서 많은 걸 배울 수 있었다. 이를테면 정답률 30% 미만의 문제는 피해야 한다든지...
