[백준] 1987번 알파벳 ★

💡문제접근

• 알고리즘 분류에는 깊이 우선 탐색이 나와 있었는데 나는 이 방법보다는 너비 우선 탐색이 더 수월하다고 판단하여 BFS를 이용해서 코드를 작성했다. 큐로 구현해보면 시간초과(TLE)가 발생하는데 집합으로 구현해보면 시간초과가 발생하지 않는다.
• 자료구조에 대한 시간복잡도를 잘 알고 이를 활용해야 할 것 같다.

📌 자료구조 시간복잡도 정리

• Stack 시간복잡도

• 삽입 : O(1)
• 삭제 : popO(1), removeO(N)
• 검색 : O(N)

• Queue 시간복잡도

• 삽입 : O(1)
• 삭제 : dequeueO(1), removeO(N)
• 검색 : O(N)

• Deque 시간복잡도

• 삽입 : O(1)
• 삭제 : popO(1), popleftO(1) removeO(N)
• 검색 : O(N)

Q.Deque의 popleft의 시간복잡도는 O(1)이고 set의 pop의 시간복잡도 역시 O(1)인데 왜 Deque로 하면 시간초과(TLE)가 발생하고 set로 하면 정상 통과될까?

A. 같은 O(1)이어도 set은 중복을 허용하지 않기 때문에 더 짧은 시간이 소요된다는 답이 있었다. 덕분에 이해할 수 있었다.

💡코드(메모리 : 51732KB, 시간 : 1500ms)

import sys
input = sys.stdin.readline

R, C = map(int, input().strip().split())

board = [list(input().strip()) for _ in range(R)]
# 초기값이 1인 이유 : (0, 0)부터 시작하면 최소 1개의 알파벳이 나올 수 있으므로...
answer = 1

def BFS(a, b):
    global answer
    queue = set([(a, b, board[a][b])])
    while queue:
        x, y, alphabet = queue.pop()
        dx = [0, 1, 0, -1]
        dy = [-1, 0, 1, 0]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= R or ny < 0 or ny >= C:
                continue
            if 0 <= nx < R and 0 <= ny < C:
                if board[nx][ny] not in alphabet:
                    queue.add((nx, ny, alphabet + board[nx][ny]))
                    answer = max(answer, len(alphabet)+1)

BFS(0, 0)
print(answer)

💡소요시간 : 48m