[백준] Python - 알파벳

1987번: 알파벳

 

백준의 그래프 탐색 문제 알파벳이다.

이 문제는 DFS와 BFS 두 가지 방법으로 접근했다.

 

DFS 같은 경우는 재귀를 사용하여 visited 집합에 방문 여부를 저장하는 방식을 사용했다.

DFS와 BFS가 모두 인접 행렬/인접 리스트 각각에서 시간 복잡도가 같은 걸로 알고 있는데 DFS 방식은 PyPy3로 해결할 수 있었고 Python3로는 시간초과가 발생했다.

 

BFS를 사용한 방식은 조금의 변형이 있었다.

일반적으로 우리는 FloodFill과 같은 알고리즘을 BFS로 구현하면서 상하좌우의 좌표를 지속적으로 갱신하면서 이동한다.

여기서 데크를 사용하는 경우가 많다.

이번 문제의 경우 사용할 큐를 데크 대신 집합을 사용했다.

좌표와 누적된 문자열의 길이를 집합에 저장하고 그 최대값 길이를 갱신하는 방식을 택했다.

 

여기서 조금 더 나은 시간복잡도를 원한다면 집합에 저장하는 형태를 한 번더 변형하는 방식을 택할 수도 있을 것 같다.

 

현재는 아래와 같은 튜플을 집합에 저장한다.

여기서 3번째 인덱스는 문자열이 저장되는데 이를 in을 통해 특정 문자를 찾는다면 O(n)의 시간 복잡도를 가질 것이다.

# (x좌표, y좌표, 출발지부터 x, y까지의 누적 경로) 
Q = { (x, y, G[x][y] + v) }
a, b, c = Q.pop()

# 방문 여부 파악하기
if G[i][j] in c:

 

이를 개선하는 방식을 생각해보면 방문 경로를 문자열로 저장하지 않고 집합으로 저장하여 in을 통해 접근하면 O(1)의 시간 복잡도를 가진다.

# (x좌표, y좌표, 출발지부터 x, y까지의 누적 경로) 
Q = { (x, y, {G[x][y], v}) }
a, b, c = Q.pop()

# 방문 여부 파악하기
if G[i][j] in c:

 

GitHub - Floodnut/algorithm: 알고리즘 풀이 모음